1. 조건
- 0 : 이동 가능 / 1 : 이동 불가능
- (1,1) → (N,M) 으로 이동
- 한개까지 벽 부시기 가능
- (1,1), (N,M)은 항상 0
2. 입력
- 가로 : M, 세로 : N
3. 출력
- 최단거리 출력하되 불가능하면 -1
4. 경계값 반례
1 1
1
// 1
1 1
0
// 1
3 4
0111
1000
0000
// 6
3 4
0111
0000
0000
// 6
5. 풀이
- 0층은 벽을 안 부쉈을 때, 1층은 벽을 한개 부쉈을 때로 가정해 [2][MAX_NUM][MAX_NUM] 배열을 만든다.
- (0,0)은 무조건 0이므로 0층 [0][0]에서 탐색을 시작한다.
- (N-1, M-1)까지 도달할 수 있는 조건은 3가지이다.
ㄴ 1) 벽을 한번도 안 부쉈고 가야할 곳도 벽이 없음
ㄴ 2) 벽을 한번도 안 부쉈고 가야할 곳에 벽이 있음
ㄴ 3) 벽을 한번 부쉈고 가야할 곳에 벽이 없음
ㄴ 4) 이 외 케이스는 못 간다
- 위의 3가지 조건을 이용하여 BFS 탐색을 돌린다.
C++)
#include <iostream>
#include <algorithm>
#include <queue>
#define MAX_NUM 1002
using namespace std;
char arr[MAX_NUM][MAX_NUM];
int visited[2][MAX_NUM][MAX_NUM]; // 0 : 벽 안 부심, 1 : 벽 부심
queue<pair<char, pair<int, int>>> q;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n;
int m;
void bfs() {
while (!q.empty()) {
char floor = q.front().first; // 벽 부쉈나 안 부쉈나
int x = q.front().second.first;
int y = q.front().second.second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
// 그동안 벽을 안 부쉈고 계속 안 부심
if (floor == '0' && arr[nx][ny] == '0' && visited[0][nx][ny] == 0) {
visited[0][nx][ny] = visited[0][x][y] + 1;
q.push({ '0', {nx, ny} });
}
// 그동안 벽을 안 부쉈고 벽을 만남
else if (floor == '0' && arr[nx][ny] == '1' && visited[1][nx][ny] == 0) {
visited[1][nx][ny] = visited[0][x][y] + 1;
q.push({ '1', {nx,ny} });
}
// 벽을 한번 만났고 앞으로는 안 만남
else if (floor == '1' && arr[nx][ny] == '0' && visited[1][nx][ny] == 0) {
visited[1][nx][ny] = visited[1][x][y] + 1;
q.push({ '1', {nx,ny} });
}
// 어차피 그 외 케이스는 의미없음
}
}
}
int CheckAnswer() {
if (visited[0][n - 1][m - 1] == 0 && visited[1][n - 1][m - 1] == 0)
return -1;
else if (visited[0][n - 1][m - 1] != 0 && visited[1][n - 1][m - 1] != 0)
return min(visited[0][n - 1][m - 1], visited[1][n - 1][m - 1]);
else
return max(visited[0][n - 1][m - 1], visited[1][n - 1][m - 1]);
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
visited[0][0][0] = 1;
q.push({ '0', { 0,0 } });
bfs();
cout << CheckAnswer();
return 0;
}
Python)
import sys
from collections import deque
read = sys.stdin.readline
dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()
n, m = map(int, read().rstrip().split())
arr = [[] * m for _ in range(n)]
visited = []
for _ in range(2):
visited.append(list([0] * m for _ in range(n)))
for i in range(n):
arr[i] = list(read().rstrip())
def bfs():
while q:
isBroken, x, y = q.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 벽을 한번도 안 부쉈고 앞으로도 안 부심
if not isBroken and arr[nx][ny] == '0' and visited[0][nx][ny] == 0:
visited[0][nx][ny] = visited[0][x][y] + 1
q.append((False, nx, ny))
# 벽을 한번도 안 부쉈고 하나 부숴야함
elif not isBroken and arr[nx][ny] == '1' and visited[1][nx][ny] == 0:
visited[1][nx][ny] = visited[0][x][y] + 1
q.append((True, nx, ny))
# 벽을 한번 부쉈고 앞으로는 안 부심
elif isBroken and arr[nx][ny] == '0' and visited[1][nx][ny] == 0:
visited[1][nx][ny] = visited[1][x][y] + 1
q.append((True, nx, ny))
def CheckAnswer():
if visited[0][n-1][m-1] == 0 and visited[1][n-1][m-1] == 0:
return -1
elif visited[0][n-1][m-1] != 0 and visited[1][n-1][m-1] != 0:
return min(visited[0][n-1][m-1], visited[1][n-1][m-1])
else:
return max(visited[0][n-1][m-1], visited[1][n-1][m-1])
visited[0][0][0] = 1
q.append((False, 0, 0))
bfs()
print(CheckAnswer())'백준 2 > 그래프' 카테고리의 다른 글
| [백준 4179] 불! (C++/Python) (0) | 2020.12.08 |
|---|---|
| [백준 1261] 알고스팟 (C++) (0) | 2020.12.08 |
| [백준 11404] 플로이드 (C++/Java) (0) | 2020.12.08 |
| [백준 3055] 탈출 (C++) (0) | 2020.12.08 |
| [백준 5427] 불 (C++/Python) (0) | 2020.12.08 |