반응형

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

 

2151번: 거울 설치

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵을 입력받고, 문의 위치를 vector에 저장합니다.

 

2. pos struct를 만들어 y좌표, x좌표, 빛의 방향, 거울의 개수를 저장합니다.

 

3. visited배열에 방문 여부를 저장하고, visited [ i ][ j ][ k ]에서 i는 y좌표, j는 x좌표, k는 빛의 방향입니다.

 

4. dijkstra를 이용하여 거울의 개수가 적은 순으로 priority_queue에서 뽑고, '!'와 '#'를 만나면 pq에 넣습니다.

 

5. vector에 저장된 문의 좌표와 현재 좌표가 일치하면 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
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<queue>
#include<vector>
 
using namespace std;
 
int N;
char arr[51][51];
int visited[51][51][4];
vector<pair<int, int>> door;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
struct pos {
    int y;
    int x;
    int cnt;
    int dir;
};
 
struct cmp {
    bool operator()(pos right, pos left) {
        return left.cnt < right.cnt;
    }
};
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == '#') {
                door.emplace_back(i, j);
            }
        }
    }
 
    int y = door[0].first;
    int x = door[0].second;
 
    priority_queue<pos, vector<pos>, cmp> pq;
 
    for (int i = 0; i < 4; i++) {
        pq.push({ y,x,0,i });
    }
 
    while (!pq.empty()) {
        int y = pq.top().y;
        int x = pq.top().x;
        int cnt = pq.top().cnt;
        int dir = pq.top().dir;
        pq.pop();
 
        if (y == door[1].first && x == door[1].second) {
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[y][x][dir] == 1) continue;
        visited[y][x][dir] = 1;
 
        for (int i = 1; i < N; i++) {
            int yy = y + dy[dir] * i;
            int xx = x + dx[dir] * i;
 
            if (arr[yy][xx] == '*' || yy >= N || yy < 0 || xx >= N || xx < 0) break;
            if (arr[yy][xx] == '!') {
                if (dir == 0 || dir == 1) {
                    if (visited[yy][xx][dir] != 1) {
                        pq.push({ yy,xx,cnt+1,2 });
                        pq.push({ yy,xx,cnt+1,3 });
                    }
                }
                else {
                    if (visited[yy][xx][dir] != 1) {
                        pq.push({ yy,xx,cnt+1,0 });
                        pq.push({ yy,xx,cnt+1,1 });
                    }
                }
            }
            if (arr[yy][xx] == '#') {
                pq.push({ yy,xx,cnt });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 6087번 - 레이저 통신 (C++)  (0) 2022.11.24
[ 백준 ] 4485번 - 녹색 옷 입은 애가 젤다지? (C++)  (0) 2022.11.23
[ 백준 ] 17386번 - 선분 교차 1 (C++)  (0) 2022.11.21
[ 백준 ] 1774번 - 우주신과의 교감 (C++)  (0) 2022.11.20
[ 백준 ] 10282번 - 해킹 (C++)  (0) 2022.11.19

+ Recent posts

티스토리툴바