• 백준 3055번 탈출 :: 마이구미
    알고리즘 풀이/그래프 2017. 10. 15. 22:09

    이 글은 백준 알고리즘 문제 3055번 "탈출" 을 풀이한다.

    본인은 BFS를 활용하여 문제를 해결하였다.

    3055번 - https://www.acmicpc.net/problem/3055

    기본 DFS, BFS - http://mygumi.tistory.com/102

     

    사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

    티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

    매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

    티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

    고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

     

    결국 문제가 원하는 것은 S -> D 로 가는 최소 시간이다.

    문제에서 다음과 같은 2가지만 인지하면 된다.

     

    1. 고슴도치와 물은 상하좌우로 이동할 수 있다.
    2. 물이 찰 예정인 칸은 고슴도치가 이동할 수 없다.

     

    물이 찰 예정인 칸은 고슴도치가 이동할 수 없다는 의미는 단순히 물부터 인접한 칸을 채운 후, 고슴도치를 채우면 된다.

    물에 대해 BFS를 통해 한번 채우고, 그 다음 고슴도치에 대해 BFS를 통해 채우면 문제를 해결할 수 있다.

    돌은 신경쓰지 않으면 아무 지장이 없기 때문에, 고려하지 않는다.

     

    기본적인 BFS에 대한 이해를 하고 있다면, 쉽게 소스를 통해 풀이를 이해할 수 있을 것이다.

    긴 코드를 볼 수 있지만, 이해를 돕기 위한 것이다.

    이해한 후 스스로 줄여보길 바란다.

     

    그래프 알고리즘 문제 풀이 - 그래프 문제 카테고리

    Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/3055.java

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    static char[][] map;
    static int r, c;
    static int[] dx = { -101};
    static int[] dy = { 0-10};
    static Queue<Point> water = new LinkedList<>();
    static Queue<Point> hedgehog = new LinkedList<>();
     
    private void solve() {
        // http://mygumi.tistory.com/232
        r = sc.nextInt();
        c = sc.nextInt();
        map = new char[r][c];
     
        for (int i = 0; i < r; i++) {
            char[] input = sc.next().toCharArray();
            for (int j = 0; j < c; j++) {
                map[i][j] = input[j];
     
                if (input[j] == '*') {
                    water.add(new Point(i, j));
                }
     
                if (input[j] == 'S') {
                    hedgehog.add(new Point(i, j));
                }
            }
        }
     
        int ans = 0;
        while (true) {
            ++ans;
            if (hedgehog.size() == 0) {
                System.out.println("KAKTUS");
                return;
            }
     
            extendWater();
            if (extendHedgehog()) {
                System.out.println(ans);
                return;
            }
        }
    }
     
    public static void extendWater() {
        int size = water.size();
     
        for (int i = 0; i < size; i++) {
            Point p = water.poll();
     
            for (int j = 0; j < 4; j++) {
                int nx = dx[j] + p.x;
                int ny = dy[j] + p.y;
     
                if (<= nx && nx < c && <= ny && ny < r) {
                    if (map[ny][nx] == '.') {
                        map[ny][nx] = '*';
                        water.add(new Point(ny, nx));
                    }
                }
            }
        }
    }
     
    public static boolean extendHedgehog() {
        int size = hedgehog.size();
     
        for (int i = 0; i < size; i++) {
            Point p = hedgehog.poll();
     
            for (int j = 0; j < 4; j++) {
                int nx = dx[j] + p.x;
                int ny = dy[j] + p.y;
     
                if (<= nx && nx < c && <= ny && ny < r) {
                    if (map[ny][nx] == 'D') {
                        hedgehog.add(new Point(ny, nx));
                        return true;
                    }
                    if (map[ny][nx] == '.') {
                        map[ny][nx] = 'S';
                        hedgehog.add(new Point(ny, nx));
                    }
                }
            }
        }
        return false;
    }
     
    static class Point {
        int x;
        int y;
     
        Point(int y, int x) {
            this.x = x;
            this.y = y;
        }
    }
    cs

     

    TAG

    댓글 6

    • tjkim 2019.11.11 01:34

      질문이있습니다. BFS에 따라 고슴도치가 지나간길을 'S'로 바꿔주시는데 아마 visit배열 따로 처리안하신거라 그렇겠지요. 그런데 만약 고슴도치가 지나간길을 물을 채워야한다면 물이 채워지지않아 정상적으로 실행이안되지않나요?? 그런상황이 아예 발생할수가없는건가요?? ㅠㅠ 1시간째 코드보면서 고민하는데 이해가안갑니다 조언좀주세요

      • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.11.11 10:21 신고

        고슴도치는 물이 차는 것이 예정된 곳을 갈 수 없다고 했습니다.
        그래서 미리 물을 채우는 처리를 고슴도치 이동보다 먼저 하고 있습니다.
        그래서 고슴도치가 지나간 길에 물을 채우는 경우는 존재하지 않습니다!

    • tjkim 2019.11.11 15:04

      먼저 물을 채우고 이동하는건 알겠는데 만약 . . . . *
      x . xx
      . . . S
      이런식으로있다고했을 때 벽 떄문에 물이 채워질수있는 경우는 벽 옆의 .을 통과하는경우인데
      물론 페이즈를 진행할때 고슴도치는 저부분을 지나가있습니다만, 그 다음 영역이 고슴도치가 지나갔기 떄문에 S로표시된다면 그 다음페이즈부터는 물의 확장을 알수없지않나요?? 그 이후는 물이 확장되도 고슴도치를 따라잡을수없기떄문에 고려하지않는것뿐인가요??

      • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.11.11 16:58 신고

        말씀하신대로 고려하지않았다고 할 수 있죠.
        하지만 아예 그런 경우를 생각하지 않았습니다.
        고슴도치와 물을 독립적으로 생각했습니다.
        각자 확장해가면서, 고슴도치가 도착하지 못하는 상황이면 실패, 도착할 수 있으면 성공이라는 것만 알면 되기 때문입니다.
        둘 사이의 연관관계를 두지 않았습니다!

    • tjkim 2019.11.11 17:46

      친절한 답변감사드립니다!! 항상 알고리즘문제풀면서 많은 도움받고있습니다 ㅎㅎ

Designed by Tistory.