M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 3055 - 탈출

최대 1 분 소요

문제

백준 3055 - 탈출 풀러가기

문제 분석

한 칸을 이동 할 때 1만큼의 시간이 걸리고, 최소 시간을 걸리는 문제이므로 가중치가 1인 bfs로 문제를 풀면 된다.

문제 풀이

  1. 전체 코드

    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
    99
    100
    101
    102
    103
    104
    105
    #include <iostream>
    #include <queue>
    #include <cstring>
     
    using namespace std;
     
    char map[50][50];
    int time[50][50];
    int stime[50][50];
     
    int dx[] = { 0,0,1,-1 };
    int dy[] = { 1,-1,0,0 };
     
    int r, c;
     
    int sr, sc, dr, dc;
     
    queue<pair<int, int>> q;
     
    int main() {
     
        memset(time, -1, sizeof(time));
        memset(stime, -1, sizeof(stime));
        
        cin >> r >> c;
     
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                cin >> map[i][j];
     
                if (map[i][j] == '*') {
                    q.push(make_pair(i, j));
                    time[i][j] = 0;
                }
                else if (map[i][j] == 'S') {
                    sr = i;
                    sc = j;
                    map[i][j] = '.';
                }
                else if (map[i][j] == 'D') {
                    dr = i;
                    dc = j;
                }
            }
        }
     
        while (!q.empty()) {
            int cr = q.front().first;
            int cc = q.front().second;
     
            q.pop();
     
            for (int k = 0; k < 4; k++) {
                int nr = cr + dy[k];
                int nc = cc + dx[k];
     
                if (nr >= 0 && nr < r && nc >= 0 && nc < c) {
                    if (map[nr][nc] == '.' && time[nr][nc] == -1) {
                        time[nr][nc] = time[cr][cc] + 1;
                        q.push(make_pair(nr, nc));
                    }
                }
            }
        }
     
        q.push(make_pair(sr, sc));
        stime[sr][sc] = 0;
     
        while (!q.empty()) {
            int cr = q.front().first;
            int cc = q.front().second;
     
            q.pop();
     
            for (int k = 0; k < 4; k++) {
                int nr = cr + dy[k];
                int nc = cc + dx[k];
     
                if (nr >= 0 && nr < r && nc >= 0 && nc < c) {
     
                    if (map[nr][nc] == 'X' || stime[nr][nc] != -1) {
                        continue;
                    }
     
                    if ((stime[cr][cc] + 1 >= time[nr][nc]) && time[nr][nc] != -1) {
                        continue;
                    }
     
                    
                    q.push(make_pair(nr, nc));
                    stime[nr][nc] = stime[cr][cc] + 1;
                }
            }
     
        }
     
        if (stime[dr][dc] == -1) {
            cout << "KAKTUS";
        }
        else {
            cout << stime[dr][dc];
        }
     
        return 0;
    }
    		cs
  • 47~64 줄 : 물이 차는 시간을 구하기 위해 bfs를 진행
  • 69~95 줄 : 고슴도치가 비버의 굴로 가는 최단 시간을 구함.
    • 85 줄 : 만약, 이동하려는 칸의 물이 찬 시간이 현재 칸에서 고슴도치의 시간에서 +1을 한 것 보다 같거나 크다면, 이동 할 수 없다.

추가 테스트 케이스

추가적인 테스트 케이스 보러가기

이곳에서 문제에 주어진 기본적인 테스트 케이스 말고, 다른 테스트 케이스를 이용해 볼 수 있다.

연관 문제

백준 7576 - 토마토






아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고