CSES PS - Grid Paths

https://cses.fi/problemset/task/1625/

백트래킹 문제. 아이디어가 안떠올라서 답확인함.

 

<문제설명>

7*7 공간에서 (0,0) ~ (6,0)까지 갈 때 경로가 ?,L,R,U,D 총 48자로 주어진다. 이때 ?대신 아무 방향이나 사용할 수 있을 때 가능한 경로의 수를 모두 구하는 문제.

 

<생각>

?가 48개 있을 때 백트래킹 없이 dfs하면 4^48만큼의 시간이 걸리므로 백트래킹이라고 생각하지 않았다. U 9개 D 15개, R 12개, L 12개의 적절한 순열인 줄 알았지만 아니었다.

 

 

<문제풀이>

(빨간색은 방문할 수 없는 지점(벽너머거나, 방문했거나), 파란색은 방문할 수 있는 지점(y>0 && y<7))

현재 상태로 진입하지 전에 'R' 명령을 받았다고, 위아래로 방문할 수 있고, (cy,cx+1)은 방문할 수 없다면 이 경로는 불가능한 경로이다.

L, R, U, D에 대해 모두 위와같이 가지치기를 해주면 되는 문제이다.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int dy[]{ 1, -1, 0 ,0 }, dx[]{ 0,0,-1,1 };

string s;
bool visited[8][8]; //0,0~7,0

int ans = 0;
void go(int cy, int cx, int k, char m) {
	if (cy == 6 && cx == 0) {
		if (k == 48) ans++;
		return;
	}
	
	if (m == 'L' && (cx == 0 || visited[cy][cx - 1]) && cy > 0 && cy < 6 && !visited[cy - 1][cx] && !visited[cy + 1][cx]) return;
	if (m == 'R' && (cx == 6 || visited[cy][cx + 1]) && cy > 0 && cy < 6 && !visited[cy - 1][cx] && !visited[cy + 1][cx]) return;
	if (m == 'U' && (cy == 0 || visited[cy - 1][cx]) && cx > 0 && cx < 6 && !visited[cy][cx - 1] && !visited[cy][cx + 1]) return;
	if (m == 'D' && (cx == 0 || visited[cy + 1][cx]) && cx > 0 && cx < 6 && !visited[cy][cx - 1] && !visited[cy][cx + 1]) return;

	visited[cy][cx] = true;

	if (s[k] == '?') {
		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i], nx = cx + dx[i];
			if (!visited[ny][nx] && ny >= 0 && nx >= 0 && ny < 7 && nx < 7)
				go(ny, nx, k + 1, "DULR"[i]);
		}
	}
	else {
		int i;
		for (int j = 0; j < 4; j++)
			if (s[k] == "DULR"[j]) i = j;
		int ny = cy + dy[i], nx = cx + dx[i];
		if (!visited[ny][nx] && ny >= 0 && nx >= 0 && ny < 7 && nx < 7) 
			 go(ny, nx, k + 1, s[k]);
	}

	visited[cy][cx] = false;
}

int main() {
	cin >> s;
	go(0, 0, 0, 0);
	cout << ans << '\n';
}

 

---

 

더 나아가서, 맨 위에 설명한 네가지 상황은 사실 위 두 상황과 같은 상황이다. 재귀함수에 이전 명령을 전해줄 필요가 없어졌다.

 

하지만 이를 0base visited 배열로 처리하자면 코드가 굉장히 길어진다.

if (cy > 0 && cy < 6 && !visited[cy + 1][cx] && !visited[cy - 1][cx] && (cx == 6 || visited[cy][cx + 1]) && (cx == 0 || visited[cy][cx - 1])) return;
if ((cy == 0 || visited[cy - 1][cx]) && (cy == 6 || visited[cy + 1][cx]) && cx > 0 && cx < 6 && !visited[cy][cx + 1] && !visited[cy][cx - 1]) return;

 

1base visited 배열에 바운더리를 넘어가는 부분을 모두 방문처리를 해준다면 좀더 간결한 코드로 구현할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int dy[]{ 1, -1, 0 ,0 }, dx[]{ 0,0,-1,1 };

string s;
bool visited[9][9]; //1,1~7,1

int ans = 0;
void go(int cy, int cx, int k) {
	if (cy == 7 && cx == 1) {
		if (k == 48) ans++;
		return;
	}

	if (!visited[cy + 1][cx] && !visited[cy - 1][cx] && visited[cy][cx + 1] && visited[cy][cx - 1]) return;
	if (visited[cy + 1][cx] && visited[cy - 1][cx] && !visited[cy][cx + 1] && !visited[cy][cx - 1]) return;

	visited[cy][cx] = true;

	if (s[k] == '?') {
		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i], nx = cx + dx[i];
			if (!visited[ny][nx] && ny >= 1 && nx >= 1 && ny < 8 && nx < 8)
				go(ny, nx, k + 1);
		}
	}
	else {
		int i;
		for (int j = 0; j < 4; j++)
			if (s[k] == "DULR"[j]) i = j;
		int ny = cy + dy[i], nx = cx + dx[i];
		if (!visited[ny][nx] && ny >= 1 && nx >= 1 && ny < 8 && nx < 8)
			go(ny, nx, k + 1);
	}

	visited[cy][cx] = false;
}

int main() {
	cin >> s;
	for (int i = 0; i <= 8; i++) visited[0][i] = visited[i][0] = visited[8][i] = visited[i][8] = 1;
	go(1, 1, 0);
	cout << ans << '\n';
}