5213 - 과외맨 (Java)

박세건·2025년 5월 3일

알고리즘 문제 해결

목록 보기

50/50

🧩 백준 5213: 과외맨

문제 링크

📌 문제 요약

과외맨이 고대 마야 사원에 있는 과외 노트를 찾기 위해 도미노 타일로 만들어진 다리를 건넌다.
타일은 (왼쪽 숫자, 오른쪽 숫자)로 구성된 도미노 조각.
인접한 타일로 이동하려면 공유하는 면의 숫자가 같아야 하며, 이동은 상하좌우로만 가능.
목표는 첫 번째 타일에서 시작해 마지막 줄의 마지막 타일에 도달하는 최단 경로(타일 개수 기준) 를 구하는 것이다.
만약 마지막 타일에 도달할 수 없다면 도달 가능한 가장 큰 번호의 타일까지 이동하는 경로를 출력해야 한다.

🧠 문제 접근

✅ 초기 접근: 낱개 단위로 BFS

타일이 2칸으로 구성되어 있으니, 각 칸을 방문하며 BFS를 돌면 되지 않을까?
같은 숫자라면 이동 가능하니, map[x][y] == map[nx][ny] 조건만 걸면 될 것 같은데?

처음엔 각 칸을 노드로 보고 4방 탐색하는 일반적인 BFS 방식으로 접근
하지만 문제의 조건은 타일 단위로 이동하는 것이다.
즉, 같은 타일 안에서는 숫자가 달라도 이동 가능해야 한다.
단순한 숫자 비교만으로는 타일 내부 이동이 불가능 → ❌ 오답 발생

🚨 문제점

❗ 낱개 BFS의 문제점

(x, y)만 보고 주변 탐색을 하다보니 같은 타일에 있는 두 칸을 함께 처리하지 못함
타일 3이 (1,1)-(1,2)라면 (1,1)을 방문해도 (1,2)를 자동으로 방문처리하지 않음
그래서 타일 전체를 방문했다는 보장이 없어 경로가 누락됨

🔁 개선 방법

✅ 타일 단위 BFS로 변경

타일을 구성하는 두 칸을 동시에 큐에 넣어 방문 처리
한 타일 내의 두 칸 중 하나를 방문하면 나머지도 바로 방문
다음 타일로 넘어갈 땐, 공유 면의 숫자가 같은 경우에만 이동

💡 핵심 아이디어

getTileNum(x, y) 함수로 현재 좌표가 속한 타일 번호를 빠르게 구할 수 있도록 구현
beforePoint[tileNum] = prevTileNum 방식으로 경로 추적

✅ 구현 과정 요약

맵 구성
- 입력을 받을 때 타일마다 좌표 2개에 같은 타일 번호가 들어가도록 설정
- 짝수 줄과 홀수 줄의 타일 수가 다르기 때문에 위치 조정 필요
BFS 시작
- 타일 1에서 시작
- 현재 좌표에서 4방 탐색하며 다음 타일과의 공유 면이 같을 경우 이동
같은 타일 내부 이동
- (x, y)의 다른 면 좌표도 같이 큐에 넣어줌
도달 불가능 시 가장 큰 번호의 타일에 도달하도록 경로 저장
결과 출력
- 도착한 타일에서 beforePoint[] 배열로 경로 역추적

🧪 예제 테스트

예제 입력:

예제 출력:

7
1 2 7 12 17 22 23

✅ 최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    private static StringTokenizer st;
    private static StringBuilder answerString = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, M;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private static int[] beforePoint;

    private static int totalCnt;

    public static void main(String[] args) throws IOException {
        inputSetting();
        solution();
        System.out.println(answerString);
    }

    private static void solution() {
        Queue<int[]> queue = new ArrayDeque<>();
        int maxTileNum = 1;

        queue.add(new int[]{0, 0});
        queue.add(new int[]{0, 1});
        visited[0][0] = visited[0][1] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];

            int curTileNum = getTileNum(x, y);
            maxTileNum = Math.max(maxTileNum, curTileNum);

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

                if (dx < 0 || dx >= N || dy < 0 || dy >= M) continue;
                if (visited[dx][dy] || map[dx][dy] <= 0) continue;

                int nextTileNum = getTileNum(dx, dy);
                if (map[x][y] != map[dx][dy]) continue;

                visited[dx][dy] = true;
                queue.add(new int[]{dx, dy});

                // 같은 타일의 다른 면도 같이 방문
                if (dy - 1 >= 0 && getTileNum(dx, dy - 1) == nextTileNum && !visited[dx][dy - 1]) {
                    visited[dx][dy - 1] = true;
                    queue.add(new int[]{dx, dy - 1});
                } else if (dy + 1 < M && getTileNum(dx, dy + 1) == nextTileNum && !visited[dx][dy + 1]) {
                    visited[dx][dy + 1] = true;
                    queue.add(new int[]{dx, dy + 1});
                }

                if (beforePoint[nextTileNum] == 0) {
                    beforePoint[nextTileNum] = curTileNum;
                }
            }
        }

        Stack<Integer> stack = new Stack<>();
        int cnt = 1;
        while (maxTileNum != 1) {
            stack.add(maxTileNum);
            maxTileNum = beforePoint[maxTileNum];
            cnt++;
        }
        stack.add(1);
        answerString.append(cnt).append("\n");
        while (!stack.isEmpty()) {
            answerString.append(stack.pop()).append(" ");
        }
    }

    private static int getTileNum(int x, int y) {
        if (x % 2 == 1) {
            return ((x - 1) / 2) * (2 * N - 1) + N + ((y - 1) / 2) + 1;
        } else {
            return (x / 2) * (2 * N - 1) + (y / 2) + 1;
        }
    }

    private static void inputSetting() throws IOException {
        N = Integer.parseInt(br.readLine());
        M = 2 * N;
        map = new int[N][M];
        visited = new boolean[N][M];
        beforePoint = new int[(N + N - 1) * (N / 2) + (N % 2) * N + 1];

        int total = (N + N - 1) * (N / 2) + (N % 2) * N;
        int tmp = 0;

        for (int i = 1; i < N; i += 2) {
            map[i][0] = map[i][M - 1] = -1;
            visited[i][0] = visited[i][M - 1] = true;
        }

        for (int i = 0; i < total; i++) {
            st = new StringTokenizer(br.readLine());
            while (map[tmp / M][tmp % M] == -1) tmp++;
            map[tmp / M][tmp % M++] = Integer.parseInt(st.nextToken());
            map[tmp / M][tmp % M++] = Integer.parseInt(st.nextToken());
        }
    }
}

🔚 마무리

이 문제를 풀면서 타일 단위의 경로 탐색이 낱개 탐색과는 본질적으로 다르다는 점을 확실히 느꼈다.
특히 타일 구조상 BFS 구현이 단순 숫자 비교만으로는 부족하다는 것을 깨달았고,
"타일 내부 연결 보장" + "타일 간 공유면 숫자 일치"라는 조건을 잘 반영하는 것이 핵심이었다.

박세건

멋있는 사람 - 일단 하자

이전 포스트