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

 

17244번: 아맞다우산

경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출

www.acmicpc.net

챙겨야 하는 물건은 최대 5개이므로 bfs + 비트마스킹이 가능합니다.

visit[x][y][bit]: 좌표 (x, y)에 도착했을 때 찾은 물건의 비트가 bit인 경우의 방문 처리입니다.

비트를 어떻게 할지 고민하다가 chk배열을 사용하여 해당 좌표에 있는 물건의 비트를 정해주었습니다.

나가는 문에 도착했을 때 모든 물건을 찾았을 때만 t를 출력합니다.

 

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
#include <iostream>
#include <queue>
#define MAX 50
using namespace std;
typedef pair<pair<int, int>, int> pii;
 
queue<pii> q;
char list[MAX][MAX];
bool visit[MAX][MAX][1 << 5];
int chk[MAX][MAX];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, bit;
 
void bfs() {
    for (int t = 1; !q.empty(); t++) {
        int qsize = q.size();
        while (qsize--) {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int cnt = q.front().second;
            q.pop();
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
                int ncnt = cnt;
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (list[nx][ny] == 'X') {
                    int b = chk[nx][ny];
 
                    ncnt |= b;
                }
                if (list[nx][ny] == '#' || visit[nx][ny][ncnt]) continue;
 
                if (list[nx][ny] == 'E' && ncnt == bit) {
                    cout << t << '\n';
                    return;
                }
 
                q.push({ {nx,ny}, ncnt });
                visit[nx][ny][ncnt] = true;
            }
        }
    }
}
 
void input() {
    int cnt = 0;
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
            if (list[i][j] == 'S') {
                q.push({ {i,j},0 });
                visit[i][j][0] = true;
            }
            else if (list[i][j] == 'X') {
                chk[i][j] = (1 << cnt);
                cnt++;
            }
        }
    }
 
    bit = (1 << cnt) - 1;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    bfs();
 
    return 0;
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 5547 일루미네이션  (0) 2022.05.15
boj 16932 모양 만들기  (0) 2022.05.14
boj 1194 달이 차오른다, 가자.  (0) 2021.04.21
boj 17471 게리맨더링  (0) 2021.04.16
boj 2573 빙산  (0) 2021.04.05

+ Recent posts

티스토리툴바