백준[BOJ] 2178번(미로 탐색) C++, Python
문제 링크: https://www.acmicpc.net/problem/2178
문제 설명
N x M크기의 배열로 표현되는 미로가 있다. 미로의 맨 왼쪽 위(0,0)에서 출발하여 맨 오른쪽 아래(n,m)의 위치로 이동할 때 지나야 하는 최소 칸 수를 구해야 한다.
1은 이동할 수 있는 칸이고 0은 이동할 수 없는 칸이다.
Ex) 4X6
1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1
이렇게 미로가 주어졌을때, 이동하는 과정을 살펴보자
1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1
처음에 0,0에서 시작하고 방문처리를 한다. 사면을 확인했을때 바로 밑에 있는 칸만 1이므로 여기로만 이동할 수 있고 이동한 후 방문처리 한다.
1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1
다시 사면을 확인한다. 위쪽은 이미 방문처리 했으므로 가지 못하고 바로 아래쪽에 있는 칸이 1이므로 여기로 이동한 후 방문처리 한다.
1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1
계속 반복하면
1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1
이렇게 된다.
여기까지 이동한 칸의 개수를 세면 15가 결과로 나온다.
문제 접근
인접한 칸으로만 이동을 해야하므로 BFS를 이용해서 풀어야겠다고 생각했다.
상하좌우로만 이동할 수 있으므로 dx dy 테크닉을 이용했다.
dx, dy테크닉이란?
현재 좌표에서 오른쪽으로 이동하면 x좌표만 +1이 되고 왼쪽으로 이동하면 x좌표만 -1이 된다. 이렇게 x와 y의 이동 좌표를 배열로 선언해두는 것이다.
ex) int dx[]={-1,0,1,0} int dy[]={0,-1,0,1}
이렇게 현재 좌표에서 4 방향을 탐색해 해당 좌표가 1이면(이동 가능하면) 이동하고 방문처리해준다. BFS이므로 큐를 이용해 현재 정점을 큐에 넣고 방문처리해준다. 더 이상 방문한 정점이 없을 때까지(큐가 빌 때까지) 반복해준다. 큐에 넣은 현재 정점은 방문처리 되었으므로 pop 해주고 현재 정점의 인접한 정점을 찾아서 큐에 넣어주고 그 인접한 정점들에 대해서 탐색하며 방문처리를 해준다.
C++ Code
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
#include <iostream>
#include <queue>
#include <string>
using namespace std;
bool visited[100][100];
int rx[] = { 0,0,1,-1 };
int ry[] = { 1,-1,0,0 };
int n, m;
int ans;
int graph[100][100];
void bfs(int x, int y) {
queue<pair<int,int>>q;
q.push({ x,y }); //큐에 좌표를 저장해줌
visited[x][y] = true;
while (!q.empty()) {
int s = q.size(); //큐의 size 저장해줌. 후에 이동한 칸 수 세기 위함.
for (int i = 0; i < s; i++) {
int x = q.front().first; //큐의 맨 앞에 있는 x 좌표 저장
int y = q.front().second; //쿠의 맨 앞에 있는 y 좌표 저장
q.pop(); //방문처리 되었으므로 pop해줌
if (x == n - 1 and y == m - 1) { //좌표 값이 n,m이라면
cout << ans; //이동한 칸의 개수 출력
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + rx[i]; //좌표 이동
int ny = y + ry[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) { //범위 벗어나면 계속 다른 좌표 탐색
continue;
}
if (visited[nx][ny] || graph[nx][ny]==0) { //방문되었거나 이동할 수 없는 좌표이면(좌표 값이 0이면) 계속 다른 좌표를 탐색
continue;
}
q.push({ nx,ny }); //방문되지 않았고 범위 내의 이동할 수 있는 좌표이면(좌표 값이 1이면) 큐에 넣어주고
visited[nx][ny] = true; //방문처리해줌
}
}
++ans; //이동한 칸의 개수 증가
}
}
int main() {
cin >> n >> m;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
for (int j = 0; j < m; j++) {
graph[i][j] = s[j] - '0'; //입력 받은 값을 이차원 배열에 표현해주며 미로 만듬. 문자형태이므로 숫자로 변환
}
}
bfs(0, 0); //시작 위치는 맨 왼쪽 위(이차원 배열로 생각하면 (0,0)이다.)
}
Python Code
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
from collections import deque
def bfs(x,y):
global count
queue=deque()
queue.append((x,y))
visited[x][y]=True
while queue:
s=len(queue)
for i in range(s):
x,y=queue.popleft()
if x==n-1 and y==m-1:
print(count+1)
return
for i in range(4):
wx=dx[i]+x
wy=dy[i]+y
if wx<0 or wx >=n or wy<0 or wy>=m:
continue
if graph[wx][wy]==0 or visited[wx][wy]==True:
continue
queue.append((wx,wy))
visited[wx][wy]=True
count+=1
n,m=map(int,input().split())
graph=[[0]*100 for _ in range(100)]
visited=[[False]*100 for _ in range(100)]
for i in range(n):
s = input().strip()
for j in range(m):
graph[i][j] = int(s[j])
dx=[0,0,1,-1]
dy=[1,-1,0,0]
count=0
bfs(0,0)
