[백준] 5213. 과외맨

March 14, 2021 7 분 소요

문제 링크

[백준] 5213. 과외맨

풀이 과정

BFS 탐색 문제입니다.

static class Tile {
    int idx, leftValue, rightValue;

    public Tile(int idx, int leftValue, int rightValue) {
        this.idx = idx;
        this.leftValue = leftValue;
        this.rightValue = rightValue;
    }
}

Tile 클래스 는 입력받는 타일의 정보들을 저장하기 위해 사용됩니다. 타일의 번호, 타일 왼쪽 조각의 숫자, 타일 오른쪽 조각의 숫자로 이루어져 있습니다.

public static void main(String[] args) {
    ...
    for (int idx = 1; idx <= N * N - N / 2; idx++) {
        Tile tile = new Tile(idx, sc.nextInt(), sc.nextInt());
        tiles.add(tile);
    }
    ...
}

입력받은 값으로 Tile 객체를 생성하면서 동시에 tiles 라는 이름의 리스트에 담아둡니다. 이후, 이 타일 정보들은 2차원 배열 map 을 그리는 데에 사용됩니다.

public static void main(String[] args) {
    ...
    for (int idx = 1; idx <= N * N - N / 2; idx++) {
    Tile tile = new Tile(idx, sc.nextInt(), sc.nextInt());
    tiles.add(tile);
    }

    setMap();
    ...
}

입력을 통해 모든 타일 정보를 얻었으면, setMap 메소드 를 호출해 2차원 배열 map 에 타일 정보를 저장해둡니다.

static Point[][] map;

public static void main(String[] args) {
    ...
    map = new Point[N][2 * N];
    ...
}

static class Point {
    int x, y, idx, value;
    boolean isLeft;

    public Point(int x, int y, int idx, int value, boolean isLeft) {
        this.x = x;
        this.y = y;
        this.idx = idx;
        this.value = value;
        this.isLeft = isLeft;
    }
}

2차원 배열 map 은 문제의 조건에 따라 N x 2 * N 크기를 갖습니다. map은 각 요소가 Point 클래스 객체로 이루어져 있으며, 해당 객체는 타일 조각의 x와 y 좌표, 타일의 인덱스 번호, 타일 조각 값, 왼쪽 조각인지 오른쪽 조각인지에 대한 정보를 저장하는 5개의 멤버 변수를 갖습니다.

static void setMap() {
    Tile tile;
    int idx = 0;

    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            for (int j = 0; j < 2 * N; j += 2) {
                tile = tiles.get(idx++);
                map[i][j] = new Point(i, j, tile.idx, tile.leftValue, true);
                map[i][j + 1] = new Point(i, j + 1, tile.idx, tile.rightValue, false);
            }
        } else {
            for (int j = 1; j < 2 * N - 1; j += 2) {
                tile = tiles.get(idx++);
                map[i][j] = new Point(i, j, tile.idx, tile.leftValue, true);
                map[i][j + 1] = new Point(i, j + 1, tile.idx, tile.rightValue, false);
            }
        }
    }
}

setMap 메소드 는 짝수 행, 홀수 행 나누어서 시작 열을 다르게 설정하고, 각 요소에 타일 조각 정보들을 저장하는 작업을 수행합니다.

public static void main(String[] args) {
    ...
    for (int idx = 1; idx <= N * N - N / 2; idx++) {
        Tile tile = new Tile(idx, sc.nextInt(), sc.nextInt());
        tiles.add(tile);
    }

    setMap();
    int idx = bfs();
    ...
}

map 이 완성되었으면 BFS 탐색을 수행합니다.

static int bfs() {
    int max = 1;

    Queue<Point> queue = new LinkedList<>();
    visit[0][0] = true;
    visit[0][1] = true;

    queue.add(map[0][0]);
    queue.add(map[0][1]);

    while (!queue.isEmpty()) {
        Point now = queue.poll();

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

            if (!inRange(nx, ny) || map[nx][ny] == null || visit[nx][ny]) continue;

            if (now.value == map[nx][ny].value) {
                if (parent[map[nx][ny].idx] == 0) parent[map[nx][ny].idx] = map[now.x][now.y].idx;

                max = Math.max(max, map[nx][ny].idx);

                visit[nx][ny] = true;
                queue.add(new Point(nx, ny, map[nx][ny].idx, map[nx][ny].value, map[nx][ny].isLeft));

                if (map[nx][ny].isLeft) {
                    visit[nx][ny + 1] = true;
                    queue.add(new Point(nx, ny + 1, map[nx][ny].idx, map[nx][ny + 1].value, false));
                } else {
                    visit[nx][ny - 1] = true;
                    queue.add(new Point(nx, ny - 1, map[nx][ny].idx, map[nx][ny - 1].value, true));
                }
            }
        }
    }

    return max;
}

bfs 메소드 는 현재 타일 조각과 같은 값을 가진 상하좌우 네 방향으로 연결되어 있는 타일 조각들에 대해 BFS 탐색을 수행고, 탐색하는 동안 만난 가장 큰 타일 번호인 max 를 리턴합니다.

BFS 탐색은 다음의 순서로 이뤄집니다.

먼저, 1번 타일의 왼쪽 조각과 오른쪽 조각을 모두 큐에 담아줍니다.
각 조각에 대해 상하좌우 네 방향의 타일 조각들에 대해 방문한 적이 없고, 그 값이 같은 조각들을 찾습니다.
다음 조각이 포함된 타일의 부모가 설정되지 않았다면, 현재 조각의 타일 번호로 설정해줍니다. 이 작업은 밑에서 설명하겠습니다.
다음 조각의 타일 번호가 더 높을 수도 있으니, max 값 갱신을 시켜주고, 방문처리를 한 후 큐에 담아줍니다.
다음 조각이 포함된 타일에 대하여, 남은 부분 조각도 방문처리를 한 후에 큐에 담아줍니다.

static int[] parent;

public static void main(String[] args) {
    ...
    parent = new int[N * N - N / 2 + 1];
    ...
    
    int idx = bfs();
    Stack<Integer> path = new Stack<>();
    
    while (idx != parent[idx]) {
        path.push(idx);
        idx = parent[idx];
    }
    
    System.out.println(path.size());
    while (!path.isEmpty())
        System.out.print(path.pop() + " ");
}

1차원 배열 parent 는 문제가 요구하는 가장 짧은 경로를 출력하기 위해 사용됩니다. BFS 로 인접한 타일들을 우선적으로 탐색하므로, 최초로 만나는 다음 타일의 부모로 바로 이전에 탐색된 타일의 번호를 설정해줄 수 있습니다.

다음은 parent 가 어떻게 사용되는 지에 대한 설명입니다.

parent 는 N * N - N / 2 + 1 크기를 가지며, 이는 N을 기반으로 만들 수 있는 타일의 총 개수를 의미합니다.
bfs 메소드 로 반환받은 가장 큰 타일 번호를 기준으로, 경로를 역으로 추적합니다.
BFS 탐색을 통해 각 타일이 최초로 방문될 때 어느 타일로부터 왔는지를 저장해두고, 이를 스택에 역으로 저장해둔 뒤, 하나씩 꺼내어 나열하게 되면, 하나의 가장 짧은 경로(여럿 있을 수 있음)가 됩니다.

입력 예)
5
1 4
4 5
5 2
2 1
5 6
3 4
4 6
4 1
1 4
5 2
3 4
4 3
1 2
2 1
1 2
2 4
4 3
6 2
6 5
4 3
6 4
4 2
2 3

코드를 처음 짤 때, 타일의 일부 조각 하나를 기준으로 BFS 탐색을 진행했기에, 아래와 같은 예외가 발생할 수 있었습니다.

처음엔 (0,0) 위치의 타일 조각 하나만을 큐에 넣고, 탐색 도중 만나는 조각 하나만을 큐에 담아서 틀렸습니다. 이와 같이 코드를 작성하면, 지나온 조각을 개수를 기준으로 짧은 경로를 인식해, 위 사진의 파란색 경로를 따라 이동합니다. 따라서, 정답인 빨간색 경로가 아닌 파란색 경로가 출력됩니다.

하지만, 가장 짧은 경로는 타일의 조각이 아닌 타일 자체의 개수가 기준이 되므로, 시작시 (0, 0) 뿐만 아니라 (0, 1) 타일 조각을 넣고, 이후 탐색 동안에는 다음 타일을 구성하는 내부 두 조각(좌, 우) 모두를 큐에 한 번에 담아주어야 했습니다.

코드

import java.util.*;

public class Main {
    static int N;
    static Point[][] map;
    static boolean[][] visit;
    static ArrayList<Tile> tiles;
    static int[] parent;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new Point[N][2 * N];
        visit = new boolean[N][2 * N];
        tiles = new ArrayList<>();
        parent = new int[N * N - N / 2 + 1];

        for (int idx = 1; idx <= N * N - N / 2; idx++) {
            Tile tile = new Tile(idx, sc.nextInt(), sc.nextInt());
            tiles.add(tile);
        }

        setMap();
        int idx = bfs();
        Stack<Integer> path = new Stack<>();

        while (idx != parent[idx]) {
            path.push(idx);
            idx = parent[idx];
        }

        System.out.println(path.size());
        while (!path.isEmpty())
            System.out.print(path.pop() + " ");
    }

    static void setMap() {
        Tile tile;
        int idx = 0;

        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                for (int j = 0; j < 2 * N; j += 2) {
                    tile = tiles.get(idx++);
                    map[i][j] = new Point(i, j, tile.idx, tile.left, true);
                    map[i][j + 1] = new Point(i, j + 1, tile.idx, tile.right, false);
                }
            } else {
                for (int j = 1; j < 2 * N - 1; j += 2) {
                    tile = tiles.get(idx++);
                    map[i][j] = new Point(i, j, tile.idx, tile.left, true);
                    map[i][j + 1] = new Point(i, j + 1, tile.idx, tile.right, false);
                }
            }
        }
    }

    static int bfs() {
        int max = 1;

        Queue<Point> queue = new LinkedList<>();
        visit[0][0] = true;
        visit[0][1] = true;

        queue.add(map[0][0]);
        queue.add(map[0][1]);

        while (!queue.isEmpty()) {
            Point now = queue.poll();

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

                if (!inRange(nx, ny) || map[nx][ny] == null || visit[nx][ny]) continue;

                if (now.value == map[nx][ny].value) {
                    if (parent[map[nx][ny].idx] == 0) parent[map[nx][ny].idx] = map[now.x][now.y].idx;

                    max = Math.max(max, map[nx][ny].idx);

                    visit[nx][ny] = true;
                    queue.add(new Point(nx, ny, map[nx][ny].idx, map[nx][ny].value, map[nx][ny].isLeft));

                    if (map[nx][ny].isLeft) {
                        visit[nx][ny + 1] = true;
                        queue.add(new Point(nx, ny + 1, map[nx][ny].idx, map[nx][ny + 1].value, false));
                    } else {
                        visit[nx][ny - 1] = true;
                        queue.add(new Point(nx, ny - 1, map[nx][ny].idx, map[nx][ny - 1].value, true));
                    }
                }
            }
        }

        return max;
    }

    static boolean inRange(int x, int y) {
        if (x < 0 || x > N - 1 || y < 0 || y > 2 * N - 1) return false;
        return true;
    }

    static class Tile {
        int idx, left, right;

        public Tile(int idx, int left, int right) {
            this.idx = idx;
            this.left = left;
            this.right = right;
        }
    }

    static class Point {
        int x, y, idx, value;
        boolean isLeft;

        public Point(int x, int y, int idx, int value, boolean isLeft) {
            this.x = x;
            this.y = y;
            this.idx = idx;
            this.value = value;
            this.isLeft = isLeft;
        }
    }
}

Twitter Facebook LinkedIn

김무성

[백준] 5213. 과외맨

문제 링크

풀이 과정

코드

공유하기

댓글남기기

참고

[프로그래머스] 67256. 키패드 누르기

[프로그래머스] 72410. 신규 아이디 추천

[프로그래머스] 81301. 숫자 문자열과 영단어

[JavaScript] 문자열을 정수로 변환하는 세 가지 방법