코드
|
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int N, M;
int ans = 987654321;
void m_move(pair<int, int> &K, int dir, char ch, char tmp_map[][11])
{
int x = K.first;
int y = K.second;
while (1)
{
if (tmp_map[x][y] == 'O')
break;
int nx = x + dx[dir];
int ny = y + dy[dir];
if (tmp_map[nx][ny] == '#' || tmp_map[nx][ny] == ch)
break;
x = nx;
y = ny;
}
tmp_map[K.first][K.second] = '.';
if (tmp_map[x][y] != 'O')
{
if (ch == 'R')
tmp_map[x][y] = 'B';
else
tmp_map[x][y] = 'R';
}
K = make_pair(x, y);
}
void solve(pair<int, int> R, pair<int, int> B, pair<int, int> O, bool visit[11][11][11][11], char map[11][11], int cnt)
{
if (B == O || cnt > 10)
return ;
else if (R == O)
{
ans = min(ans, cnt);
return ;
}
for(int i=0; i<4; i++)
{
pair<int, int> nR = R, nB = B;
//상 하 좌 우
int flag = 0;
char tmp_map[11][11];
for(int j=0; j<N; j++)
for(int k=0; k<M; k++)
tmp_map[j][k] = map[j][k];
if (R.first == B.first) //현재 같은 행에 위치한 경우
{
if (i == 2)
{
if (R.second < B.second)
{
m_move(nR, i, 'B', tmp_map);
m_move(nB, i, 'R', tmp_map);
}
else
{
m_move(nB, i, 'R', tmp_map);
m_move(nR, i, 'B', tmp_map);
}
flag = 1;
}
else if (i == 3)
{
if (R.second < B.second)
{
m_move(nB, i, 'R', tmp_map);
m_move(nR, i, 'B', tmp_map);
}
else
{
m_move(nR, i, 'B', tmp_map);
m_move(nB, i, 'R', tmp_map);
}
flag = 1;
}
}
else if (R.second == B.second) //같은 열에 위치한 경우
{
if (i == 0)
{
if (R.first < B.first)
{
m_move(nR, i, 'B', tmp_map);
m_move(nB, i, 'R', tmp_map);
}
else
{
m_move(nB, i, 'R', tmp_map);
m_move(nR, i, 'B', tmp_map);
}
flag = 1;
}
else if (i == 1)
{
if (R.first < B.first)
{
m_move(nB, i, 'R', tmp_map);
m_move(nR, i, 'B', tmp_map);
}
else
{
m_move(nR, i, 'B', tmp_map);
m_move(nB, i, 'R', tmp_map);
}
flag = 1;
}
}
if (flag == 0)
{
m_move(nR, i, 'B', tmp_map);
m_move(nB, i, 'R', tmp_map);
}
if (!visit[nR.first][nR.second][nB.first][nB.second])
{
visit[nR.first][nR.second][nB.first][nB.second] = true;
bool tmp_visit[11][11][11][11];
for(int k=0; k<N; k++)
for(int kk=0; kk<M; kk++)
for(int j=0; j<N; j++)
for(int jj=0; jj<M; jj++)
tmp_visit[k][kk][j][jj] = visit[k][kk][j][jj];
solve(nR, nB, O, tmp_visit, tmp_map, cnt + 1);
}
}
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> N >> M;
pair<int ,int> R;
pair<int, int> B;
pair<int, int> O;
char map[11][11];
for(int i=0; i<N; i++)
{
cin >> map[i];
for(int j=0; j<M; j++)
{
if (map[i][j] == 'B')
B = make_pair(i, j);
else if (map[i][j] == 'R')
R = make_pair(i, j);
else if (map[i][j] == 'O')
O = make_pair(i, j);
}
}
bool visit[11][11][11][11];
int cnt = 0;
memset(visit, false, sizeof(visit));
visit[R.first][R.second][B.first][B.second] = true;
solve(R, B, O, visit, map, cnt);
if (ans == 987654321)
printf("-1\n");
else
printf("%d\n", ans);
return (0);
}
|
cs |
문제를 보자마자 dfs로 풀어야겠다 라고 생각했었는데, 생각을 잘못 했던 것 같다.
(각 R, B의 위치에 따라 그 위치에서 각 방향으로 나아가야 하므로 재귀적으로 풀어야겠다! 라고 생각했었는데, 사실은 이 문제의 경우 빨간 구슬이 탈출할 수 있는 가장 최소의 횟수를 구하는 것이므로 전체 경우에 대해서 탐색할 필요는 없다.)
bfs로 풀었다면 -> 1번 이동했을 경우, 2번 이동했을 경우 ... n번 이동했을 경우 이런식으로 탐색을 하였을 것이고, 빨간색 구슬만 탈출할 수 있는 경우를 발견했을 때 바로 break시키면 된다. (이 전에는 빨간 구슬이 탈출할 수 없음이 자명하기 때문이다.)
특이한 점은 빨간공과 파란공이 각각 bfs를 돌기 때문에 visit배열이 visit[11][11][11][11]로 선언되어야 한다.
다른 코드들과의 차이는 각 방향으로 기울였을 때 R, B가 서로 겹칠 경우를 효율적으로 구하지 못한 것 같다.
(예를 들어, 왼쪽으로 기울이는 경우 "RB순으로 놓여 있으면 R이 먼저 이동하고 B가 이동해야 한다"와 같은 로직으로 구현하였는데 둘 다 벽이 아닌 곳까지 위치시키고 현재 같은 위치에 놓여져 있다면 두 구슬이 지나온 거리가 더 짧은 것이 긴 구슬 뒤에 오게끔 구현하면 되었다.)
bfs로는 많이 풀어봤으니 dfs로 풀어봄으로써 좋은 경험을 하였으나 앞으로 문제 풀 때 "최솟값"에 대한 내용이라면 bfs를 먼저 생각하기로 하였다.
'Study > BOJ' 카테고리의 다른 글
| BOJ - 모노미노도미노 2 (0) | 2021.04.22 |
|---|---|
| BOJ - 사다리 조작(15684) (0) | 2021.04.22 |
| BOJ - 어른 상어(19237) (0) | 2021.04.21 |
| BOJ - 행성 터널(2887) (0) | 2021.04.15 |
| BOJ - 다리 만들기 2(17472) (0) | 2021.04.15 |
