[코드트리] 우리는 하나

문제링크

문제

n * n의 숫자로 되어 있는 격자에 k개의 나라를 방문하는데, 이 나라와 인접하고 차이가 u이상 d이하면 방문 할 수 있다.
이때 방문할 수 있는 최대 나라의 수는?

문제 풀이

• 나라와 인접한 나라를 찾음 -> BFS
• 최대 경우를 찾음 -> 백트래킹

문제 해결 코드

public static void find(boolean[][] visited, int cnt, int kCnt) {
    if (kCnt == k + 1) {
        max = Math.max(max, cnt);
        return;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                // 방문 상태 복사
                boolean[][] nextVisited = copyVisited(visited);
                Queue<int[]> q = new LinkedList<>();
                q.add(new int[]{i, j});
                nextVisited[i][j] = true;

                int localCnt = 1; // 현재 시작점 포함
                while (!q.isEmpty()) {
                    int[] tmp = q.poll();
                    int x = tmp[0];
                    int y = tmp[1];

                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (inRange(nx, ny) && !nextVisited[nx][ny] && diff(x, y, nx, ny)) {
                            nextVisited[nx][ny] = true;
                            q.add(new int[]{nx, ny});
                            localCnt++;
                        }
                    }
                }

                find(nextVisited, cnt + localCnt, kCnt + 1); // 백트래킹 재귀
            }
        }
    }
}

• bfs의 백트래킹 해결이 문제 해결의 요점
• 방문할 수 있는 수 -> bfs를 위해 queue에 넣을 좌표의 수
• k가 2 이상인 경우, 방문하지 않은 곳에서 출발 -> 최대의 수를 구할 수 있음