반응형

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

 

1194번: 달이 차오른다, 가자.

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 민식이의 이동을 기록할 visited [ key ][ y ][ x ] 배열을 만듭니다. 여기서 key의 최댓값은 a~f까지 총 6개이므로 $2^{6}$(=128)입니다.

 

2. bfs를 통해 이동을 하다가 a~f사이 알파벳을 만나면 현재 key에 1 << arr [ y ][ x ] - 'a'의 값을 추가해 줍니다.

 

3. 이동 중 A~F사이 알파벳을 만나면 현재 key에 1 << arr [ y ][ x ] - 'A'의 값이 존재하면 queue에 넣고, 존재하지 않는다면 넘어갑니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
char arr[51][51];
int visited[130][50][50];
int Sy, Sx;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct node {
    int y;
    int x;
    int key;
    int cnt;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == '0') {
                arr[i][j] = '.';
                Sy = i;
                Sx = j;
            }
        }
    }
 
    queue<node> q;
    q.push({ Sy,Sx,0,0 });
    visited[0][Sy][Sx] = 1;
 
    while (!q.empty()) {
        const int y = q.front().y;
        const int x = q.front().x;
        const int key = q.front().key;
        const int cnt = q.front().cnt;
        q.pop();
 
        if (arr[y][x] == '1') {
            printf("%d", cnt);
            return 0;
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (arr[yy][xx] == '.' || arr[yy][xx] == '1') {
                    if (visited[key][yy][xx] != 1) {
                        visited[key][yy][xx] = 1;
                        q.push({ yy,xx,key,cnt + 1 });
                    }
                }
                else if (arr[yy][xx] >= 'a' && arr[yy][xx] <= 'f') {
                    int newKey = key | (1 << arr[yy][xx] - 'a');
                    if (visited[newKey][yy][xx] != 1) {
                        visited[newKey][yy][xx] = 1;
                        q.push({ yy,xx,newKey,cnt + 1 });
                    }
                }
                else if (arr[yy][xx] >= 'A' && arr[yy][xx] <= 'F') {
                    if (1 << (arr[yy][xx] - 'A') & key) {
                        if (visited[key][yy][xx] != 1) {
                            visited[key][yy][xx] = 1;
                            q.push({ yy,xx,key,cnt + 1 });
                        }
                    }
                }
            }
        }
    }
 
    printf("-1");
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29
[ 백준 ] 2589번 - 보물섬 (C++)  (0) 2022.12.27
[ 백준 ] 23793번 - 두 단계 최단 경로 1 (C++)  (0) 2022.12.26
[ 백준 ] 1759번 - 암호 만들기 (C++)  (0) 2022.12.25

+ Recent posts

티스토리툴바