심화 미로 찾기

1. 미로 찾기

bool maze(int x, int y) {
	if (!inside(x, y) || board[x][y] != 0)
    	return false;
    if (x == destX && y == destY) {
    	return true;
    }
    board[x][y] = 2;
    for (int i = 0; i < 4; i++) {
		int newX = x + offset[i][0];
        int newY = y + offset[i][1];
        if (maze(newX, newY)) {
        	return true;
        }
    }
    return false;
}

2. 심화 미로 찾기

• 조건: 주인공은 절대 좌회전하지 않는다. 즉, 직진, 우회전, U-턴만 한다.

bool maze(int x, int y, int in_dir) {
	if (!inside(x, y) || board[x][y] != 0 || visited[x][y][in_dir] != 0) {
		return false;
	}

	if (x == destX && y == destY) {
		return true;
	}

	visited[x][y][in_dir] = 1;
	for (int i = 0; i < 4; i++) {
		if (i == ((in_dir + 4 - 1) % 4)) {
			continue;
		}
		int newX = x + offset[i][0];
		int newY = y + offset[i][1];
		if (maze(newX, newY, i)) {
			return true;
		}
	}
	return false;
}

3. 분석

• 3차원 배열 visited[N][N][4]
  : 해당 위치로의 진입 방향을 저장하는 배열이다.
  : index 0, 1, 2, 3은 각각 북, 동, 남, 서를 의미한다.
  : 위 그림에서 visited[3][4]의 3차원 배열은 {0, 0, 1, 0} 이다.
  : 따라서 주인공이 (3, 3)에 다시 도착한 후, (3, 4)로의 이동은 불가능하다.

• i == ((in_dir + 4 - 1) % 4
  : 북쪽 (주인공의 입장에서는 왼쪽) 으로의 이동을 말한다.
  : true인 경우 continue로 건너 뛴다.