반응형

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

 

17244번: 아맞다우산

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 입력을 받고, X를 만날 때마다 ea변수를 1씩 늘려주고, X를 ea의 값으로 바꿔줍니다.

 

2. visited [ ea ][ y ][ x ] 배열을 만들어 주운 물건을 비트마스킹을 통해 체크하고, 방문 여부를 체크합니다. 이때, ea의 최댓값은 $2^{5}$(=32)입니다.

 

3. 물건을 주울 때마다 stf 변수에 현재 물건의 번호를 통해 추가해줍니다.

 

4. 모든 물건을 다 줍고, 도착점에 도착하면 cnt를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
char arr[51][51];
int Sy, Sx;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int visited[32][51][51];
 
struct node {
    int y;
    int x;
    int cnt;
    int stf;
};
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        scanf("%s", &arr[i]);
    }
 
    int ea = 0;
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'S') {
                Sy = i;
                Sx = j;
            }
            else if (arr[i][j] == 'X') {
                arr[i][j] = '0' + ea;
                ea++;
            }
        }
    }
 
    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 cnt = q.front().cnt;
        const int stf = q.front().stf;
        q.pop();
 
        if (arr[y][x] == 'E') {
            if (stf == (1 << ea) - 1) {
                printf("%d", cnt);
            }
        }
 
        for (int i = 0; i < 4; i++) {
            const int yy = y + dy[i];
            const int xx = x + dx[i];
 
            if (yy >= 0 && yy < M && xx >= 0 && xx < N) {
                if (arr[yy][xx] >='0' && arr[yy][xx] <'5') {
                    const int temp = stf | (1 << (arr[yy][xx] - '0'));
                    if (visited[temp][yy][xx] != 1) {
                        visited[temp][yy][xx] = 1;
                        q.push({ yy,xx,cnt + 1,temp });
                    }
                }
                else if (arr[yy][xx] != '#') {
                    if (visited[stf][yy][xx] != 1) {
                        visited[stf][yy][xx] = 1;
                        q.push({ yy,xx,cnt + 1,stf });
                    }
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30
[ 백준 ] 2268번 - 수들의 합 7 (C++)  (0) 2022.12.29
[ 백준 ] 1194번 - 달이 차오른다, 가자. (C++)  (0) 2022.12.28

+ Recent posts

티스토리툴바