반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. BFS


이번 문제를 풀면서 절실히 느낀 것은, 내가 맞다고 느꼈을 때, 틀렸습니다가 몇차례 연속해서 나온다면


머리가 정지되고, 코드가 어디가 잘못된 지 정말 찾기 힘든 것 같다.


visit[y][x]라고 적어야 하는 것을 visit[y-1][x]라고 적어두고 계속 다른 곳을 찾고있어서 이 문제를 10번가량 틀린 것 같다.



이 문제는 불의 시간에 따른 흐름을 먼저 BFS로 입력해주고 그다음 존이 움직이면서 불의 시간과 비교를 해주면 된다.


따라서 불의 BFS 한 번, 존의 BFS 한 번 총 2번의 BFS를 돌려야 한다. 


이 코드의 MAP 구성은 어떻게 되어있냐면


n = 5, m = 4일때


@@@@@

@ #### @

@ #J F# @

@ #.  .# @

@ #.  .# @
@ #.  .# @

@@@@@


이런식으로 구성되어있고 결국 J가 @에 닿는 순간 탈출 할 수 있음을, 그게 아니라면 탈출 할 수 없음을 표현한다.


나머지 내용은 코드의 주석을 통해 기입해 두었다.


소스 코드 : 


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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
 
using namespace std;
 
typedef struct _INFO_
{
    int y;
    int x;
    int cnt;
}INFO;
 
char str[1005][1005];
int visit[1005][1005];
 
int jx, jy;
 
int main()
{
    int n, m;
    queue<INFO> q;
 
    scanf("%d %d", &n, &m);
 
    // 모든 맵을 @로 만든다.
    for (int i = 0; i < 1004; i++)
        for (int j = 0; j < 1004; j++)
            str[i][j] = '@';
 
    // 맵 입력
    getchar();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            scanf("%c", &str[i][j]);
    
        getchar();
    }
    
    // #이면 visit에는 -1로, J면 존의 위치 받아내고, 
    // F이면 불이난 위치의 값을 queue에 넣는다.
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (str[i][j] == '#')
                visit[i][j] = -1;
 
            else if (str[i][j] == 'J')
            {
                jx = j;
                jy = i;
            }
            else if (str[i][j] == 'F')
                q.push(INFO{ i,j,1 });
        }
    }
 
    // 불이 번지는 위치에 걸린 시간을 기입한다.
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
 
        q.pop();
 
        if (visit[y][x])
            continue;
 
        visit[y][x] = cnt;
 
        // . 또는 J는 통행 가능 길
        if (y - 1 >= 1 && !visit[y - 1][x] && (str[y - 1][x] == '.' || str[y - 1][x] == 'J'))
            q.push(INFO{ y - 1, x, cnt + 1 });
 
        if (y + 1 <= n && !visit[y + 1][x] && (str[y + 1][x] == '.' || str[y + 1][x] == 'J'))
            q.push(INFO{ y + 1, x, cnt + 1 });
 
        if (x - 1 >= 1 && !visit[y][x - 1] && (str[y][x - 1] == '.' || str[y][x - 1] == 'J'))
            q.push(INFO{ y, x - 1, cnt + 1 });
 
        if (x + 1 <= m && !visit[y][x + 1] && (str[y][x + 1] == '.' || str[y][x + 1] == 'J'))
            q.push(INFO{ y, x + 1, cnt + 1 });
    }
    
    // 존의 위치와 시간을 넣어준다.
    q.push(INFO{ jy,jx,1 });
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
 
        q.pop();
 
        // 존이 @로 왔을 때 탈출했다는 의미
        if (str[y + 1][x] == '@' || str[y - 1][x] == '@' || str[y][x - 1] == '@' || str[y][x + 1] == '@')
        {
            printf("%d", cnt);
            return 0;
        }
 
        // 불길이 도착한 시간 이상이고, visit[y][x]가 0이 아니면
        // 즉, visit[][] = 0인경우는 불이 번지지 않은 위치를 의미 
        if (visit[y][x] <= cnt && visit[y][x] != 0)
            continue;
 
        // 존의 위치를 -2로 표시
        visit[y][x] = -2;
 
        // 불보다 먼저 존이 왔거나, 그 위치의 visit[][]가 0이면
        if (y - 1 >= 1 && (visit[y - 1][x] > cnt + 1 || visit[y-1][x] == 0))
            q.push(INFO{ y - 1, x, cnt + 1 });
 
        if (y + 1 <= n && (visit[y + 1][x] > cnt + 1 || visit[y + 1][x] == 0))
            q.push(INFO{ y + 1, x, cnt + 1 });
 
        if (x - 1 >= 1 && (visit[y][x - 1] > cnt + 1 || visit[y][x - 1] == 0))
            q.push(INFO{ y, x - 1, cnt + 1 });
 
        if (x + 1 <= m && (visit[y][x + 1] > cnt + 1 || visit[y][x + 1] == 0))
            q.push(INFO{ y, x + 1, cnt + 1 });
    }
 
    // 큐를 모두 수행할 동안 @를 못만나면 결국 impossible한 것
    printf("IMPOSSIBLE");
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[2623번] 음악프로그램  (0) 2017.03.31
[5427번] 불  (0) 2017.03.31
[11780번] 플로이드 2  (0) 2017.03.30
[1168번] 조세퍼스 문제 2  (0) 2017.03.29
[1017번] 소수 쌍  (0) 2017.03.29

티스토리툴바