https://www.acmicpc.net/problem/2151
2151번: 거울 설치
첫째 줄에 집의 크기 N (1 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.
www.acmicpc.net
|
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
|
#define NSIZE 51
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
char input[NSIZE][NSIZE];
int chk[NSIZE][NSIZE][4];
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Data {
int y, x, dir, cnt;
};
int N;
int sy, sx, ey, ex;
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> input[i];
}
int flag = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (input[i][j] == '#' && flag == 0) {
input[i][j] = '.';
sy = i;
sx = j;
flag = 1;
}
else if (input[i][j] == '#' && flag == 1) {
input[i][j] = '.';
ey = i;
ex = j;
}
}
}
}
int Min = 0x7fffffff;
void bfs() {
queue<Data>q;
for (int dir = 0; dir < 4; dir++)
q.push({ sy,sx,dir,0 });
memset(chk, 0x7f, sizeof(chk));
while (!q.empty()) {
Data c = q.front(); q.pop();
Data n = c;
if (c.y == ey && c.x == ex) {
if (Min > c.cnt)Min = c.cnt;
}
n.y += dy[c.dir];
n.x += dx[c.dir];
n.dir = c.dir;
n.cnt = c.cnt;
if (n.y < 0 || n.y >= N || n.x < 0 || n.x >= N || input[n.y][n.x] == '*')continue;
if (input[n.y][n.x] == '!') {
int cdir = n.dir;
if (cdir == 0) cdir = 3;
else if (cdir == 1)cdir = 2;
else if (cdir == 2) cdir = 1;
else if (cdir == 3) cdir = 0;
if (chk[n.y][n.x][cdir] > n.cnt + 1) {
chk[n.y][n.x][cdir] = n.cnt + 1;
q.push({ n.y,n.x,cdir,n.cnt + 1 });
}
cdir = n.dir;
if (cdir == 0) cdir = 1;
else if (cdir == 1)cdir = 0;
else if (cdir == 2) cdir = 3;
else if (cdir == 3) cdir = 2;
if (chk[n.y][n.x][cdir] > n.cnt + 1) {
chk[n.y][n.x][cdir] = n.cnt + 1;
q.push({ n.y,n.x,cdir,n.cnt + 1 });
}
}
if (chk[n.y][n.x][n.dir] > n.cnt) {
chk[n.y][n.x][n.dir] = n.cnt;
q.push(n);
}
}
}
int main(void) {
init();
bfs();
cout << Min << endl;
return 0;
}
|
정말 말그대로 거울을 설치해서 빛을 원하는 위치로 이동 시킬 수 있는지 하는 문제인데 대게 dfs 문제를 많이 풀다
보면 바로 백트래킹으로 거울 넣어서 최소 찾아야지 하시는 분들이 많은데 이문제는 그렇게 하시면 런타임이 생깁니다.
혹시나 50 바이 50 일때 40개의 거울을 설치하는 경우가 있으면 그경우를 다 해야하기 때문에 리스크가 큽니다.
그래서 BFS를 이용해서 최소를 뽑아내게 다엑스트라 방식을 적용하면되는데
다엑스트라라고 해서 진짜 다엑스트라로 하라는것이 아니고 기존에 배열 체크를 1 과 0 으로 했다면
이번것은 최소를 뽑아야하니까 제일 큰 수로 체크 배열을 초기화하고 이전에 chk[n.y][n.x]==0 이면 chk[n.y][n.x]=1
으로 했다면 chk[n.y][n.x]>n.cnt 이면 chk[n.y][n.x]=n.cnt 이런식으로 해주시면 최소를 찾아서 가게 됩니다.
정말 별거 아니죠?
이문제에서는 bfs 조건을 그냥 이동하는 경우 거울을 놓을 수 있는 위치에서 거울이 놓여있을때 이동하는 경우로 이동
하는 두개의 조건을 구현하시면됩니다.
그중에서 거울설치시 이동은
이것인데 이전에
이 dx dy를 그냥 대충 쓰기만 했다면 이번에 는
0번 인덱스에는 오른쪽으로 /1번 인덱스는 아래쪽 /2번 인덱스는 왼쪽 /3번 인덱스는 위쪽 이렇게 생각하셔서
쓰시고
/ 이 거울일때
역/ 인 거울 일때 의 0번 방향은 어디로 가는지만 넣어주시면 되는데 그것이 위에 소스입니다,
이게 정말 이문제의 전부 입니다.
위 그림을 참고하여 다시 도전 해보세요.
오늘은 그럼 이만 ...
약간 비슷한 문제 하나 더 첨부해 드리겠습니다.
2019/09/19 - [분류 전체보기] - 백준 6087 레이저 통신
백준 6087 레이저 통신
https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 문제 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸..
3dpit.tistory.com
사실 위에 3차원 체크하는식으로 하시면 비슷하다고 생각합니다.
도전 또 도전해보세요.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 10798 세로읽기, 백준 11728 배열합치기 (0) | 2019.11.07 |
|---|---|
| 백준 2146 다리 만들기 (0) | 2019.10.13 |
| 백준 5213 과외맨 (0) | 2019.10.11 |
| 백준 3085 사탕게임 (0) | 2019.10.08 |
| 백준 14395 4연산 (0) | 2019.10.08 |
댓글