[BOJ] 1987 java

문제

https://www.acmicpc.net/problem/1987

 

그래프를 움직이는 느낌이라 dfs, bfs로 푸는 문제 같았다.

bfs로 풀었는데, 계속 잘못된 답을 출력했다. gpt한테 물어보니 아래와 같은 문제가 있었다.

답변을 보면서 생각해보니 "하나의 경로"를 생각하는 게 중요한 것 같았다. 하나의 경로를 완성한 후(루트->리프까지의 경로를 생성), 다른 경로를 탐색하는 느낌이라서 dfs 탐색이 적합해보였다.

 

1. visitedChars를 사용한 중복 체크와 BFS의 논리 충돌

• visitedChars를 사용하여 지나온 알파벳을 확인하는 것은 문제가 있습니다. BFS는 여러 경로를 동시에 탐색하기 때문에, 한 경로에서 추가된 알파벳이 다른 경로에서 영향을 줄 수 있습니다.
  • 예를 들어, visitedChars는 전체 경로를 공유하지만, BFS의 각 경로는 서로 독립적으로 유지되어야 합니다.
  • visitedChars는 전역 상태처럼 동작하여 예상치 못한 결과를 초래할 수 있습니다.

해결 방안:

visitedChars 대신 현재 탐색 중인 경로에서만 유효한 상태를 관리해야 합니다. 예를 들어, BFS에서 큐에 상태(현재 위치와 함께 방문한 알파벳 집합)를 저장하면 해결됩니다.

---

2. visited 배열의 비효율적인 사용

• visited 배열은 한 번 방문한 좌표를 다시 방문하지 못하게 막습니다. 하지만 이 문제에서는 경로마다 방문 가능 여부가 다를 수 있습니다. visited는 BFS가 독립된 여러 경로를 다루는 경우 부적합합니다.

해결 방안:

각 경로마다 독립적인 상태(좌표와 방문한 알파벳의 집합)를 관리해야 하며, visited 배열은 사용하지 않아야 합니다.

---

3. r+1과 c+1로 배열 크기를 지정

• 문제의 조건에 따르면 보드는 r x c 크기입니다. 하지만 배열을 r+1 x c+1로 생성하면 실제로는 필요 없는 부분이 포함됩니다.

해결 방안:

board와 visited를 정확히 r x c 크기로 지정해야 합니다.

---

4. cnt 변수의 증가 방식

• BFS에서 cnt를 단순히 증가시키는 것은 잘못된 접근입니다. 이 문제에서는 "말이 지나갈 수 있는 최대 칸 수"를 계산해야 하므로, 경로별로 지나간 칸의 수를 추적해야 합니다.

해결 방안:

BFS 큐에 현재 경로 길이도 함께 저장하고, 최대값을 추적해야 합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    // 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데,
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {-1, 1, 0, 0};

    public static int r;
    public static int c;

    public static int answer = 0;
    public static char[][] board;
    public static boolean[][] visited;
    public static List<Character> visitedChars = new ArrayList<>(); // 방문했던 알파벳 기록

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 세로 R칸, 가로 C칸으로 된 표 모양의 보드
        // 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20)
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        board = new char[r + 1][c + 1];
        visited = new boolean[r + 1][c + 1];

        // 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                board[i][j] = row.charAt(j);
            }
        }
        br.close();

        // 좌측 상단(board[0][0])에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램
        // 말이 지나는 칸은 좌측 상단의 칸도 갯수에 포함된다.
        visited[0][0]=true;
        visitedChars.add(board[0][0]);
        dfs(0, 0, 1);

        System.out.println(answer);
    }

    public static void dfs(int x, int y, int cnt) {
        answer = Math.max(answer, cnt);

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            // 1. 배열 범위를 벗어나는 경우
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            // 2. 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. || 이미 방문했던 칸
            if (visitedChars.contains(board[nx][ny]) || visited[nx][ny]) continue;

            visited[nx][ny] = true;
            visitedChars.add(board[nx][ny]);
            dfs(nx, ny, cnt+1);
            visited[nx][ny]=false;
            visitedChars.remove(visitedChars.size()-1);

        }
    }

}

 

BFS를 이용한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static class Coord {
        int x;
        int y;

        public Coord(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static char[][] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 세로 R칸, 가로 C칸으로 된 표 모양의 보드
        // 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열->board[0][0]) 에는 말이 놓여 있다.
        // 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20)
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        board = new char[r + 1][c + 1];

        // 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                board[i][j] = row.charAt(j);
            }
        }
        br.close();

        // 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램
        System.out.println(bfs(r, c));
    }

    public static int bfs(int r, int c) {
        // 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데,
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};

        Queue<Coord> queue = new ArrayDeque<>();
        List<Character> visitedChars = new ArrayList<>(); // 방문했던 알파벳 기록
        boolean[][] visited = new boolean[r + 1][c + 1]; // 방문 체크

        queue.offer(new Coord(0, 0));
        visited[0][0] = true;
        visitedChars.add(board[0][0]);
        int cnt = 1; // 말이 지나는 칸은 좌측 상단의 칸도 갯수에 포함된다.

        while (!queue.isEmpty()) {
            Coord curr = queue.poll();

            for (int dir = 0; dir < 4; dir++) {
                int nx = curr.x + dx[dir];
                int ny = curr.y + dy[dir];

                // 1. 배열 범위를 벗어나는 경우
                if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                // 2. 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. || 이미 방문했던 칸
                if (visitedChars.contains(board[nx][ny]) || visited[nx][ny]) continue;

                queue.offer(new Coord(nx, ny));
                visited[nx][ny] = true;
                visitedChars.add(board[nx][ny]);
                cnt++;
            }
        }

        return cnt;
    }
}