📚 문제
링크: https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
💡 접근법
미로에서 서로 인접한 칸으로만 이동하여 최단 거리를 구해야 하므로 BFS를 이용해야 한다.
BFS란?
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
해당 문제의 키 포인트는 2가지이다.
1. 미로 문제에서 이동을 조작하고 싶을 때 x, y에 대한 변화량을 나타내는 dx, dy를 선언한다.
문제에서 정의한 움직임은 총 4가지로, 상, 하, 좌, 우이다. 이를 dx와 dy로 나타내면 다음과 같다.
dx = [0, 0, 1, -1], dy = [1, -1, 0, 0]
또한 움직임을 적용할 때 미로의 범위를 확인해야 한다. 즉, 미로를 벗어나면 안 된다.
따라서 특정 좌표에서 미로 범위에 대한 조건문을 수행해야 한다.
2. 인접 리스트의 값 자체를 이동 횟수로 저장하면서 탐색을 진행한다. (DP와 유사한 방식)
(nx, ny) 좌표에 대하여 visited[nx][ny] == False and A[nx][ny] == 1을 만족한다면 이는 방문한 적이 없는 노드임을 뜻한다. 따라서 (x, y) 값에 +1을 한 값은 현재까지 이동한 거리(깊이)가 된다.
💻 코드
1) 전체 코드
import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
A = [[]]
visited = [[False] * (M+1) for _ in range(N+1)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
for _ in range(N):
temp = list(map(int, sys.stdin.readline().strip()))
temp.insert(0, 0)
A.append(temp)
def BFS(v, w):
queue = deque()
queue.append((v, w))
visited[v][w] = True
while queue:
node = queue.popleft()
for k in range(4):
nx = node[0] + dx[k]
ny = node[1] + dy[k]
if N >= nx > 0 and M >= ny > 0:
if not visited[nx][ny] and A[nx][ny] == 1:
visited[nx][ny] = True
queue.append((nx, ny))
A[nx][ny] = A[node[0]][node[1]] + 1
BFS(1, 1)
print(A[N][M])
2) 해설
(1) 패키지 Import
import sys
from collections import deque
파이썬 내장 함수인 input()보다 빠르게 값을 입력받기 위해 sys 라이브러리, 큐를 사용하기 위해 collections.deque 모듈을 임포트한다.
(2) 입력받기
N, M = map(int, sys.stdin.readline().split())
A = [[]]
visited = [[False] * (M+1) for _ in range(N+1)]
for _ in range(N):
temp = list(map(int, sys.stdin.readline().strip()))
temp.insert(0, 0)
A.append(temp)
도착 위치 좌표(N, M)를 입력받고, 인접 리스트(A)와 방문 리스트(visited)를 초기화한다.
for문을 순회하면서 인접 리스트, 즉 미로를 생성한다.
(3) BFS 구현
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def BFS(v, w):
queue = deque()
queue.append((v, w))
visited[v][w] = True
while queue:
node = queue.popleft()
for k in range(4):
nx = node[0] + dx[k]
ny = node[1] + dy[k]
if N >= nx > 0 and M >= ny > 0:
if not visited[nx][ny] and A[nx][ny] == 1:
visited[nx][ny] = True
queue.append((nx, ny))
A[nx][ny] = A[node[0]][node[1]] + 1
deque()를 생성하고 현재 좌표를 튜플로 큐에 삽입한다.
현재 좌표에 대해 방문 리스트를 체크하고 큐가 빌 때까지 while 문을 수행하기 시작한다.
큐에서 노드를 꺼내고 현재 노드에서 인접한 칸을 상하좌우로 탐색한다.
이때 움직임을 적용한 좌표가 1) 미로의 범위를 벗어나지 않는지 2) 방문한 적이 없는 좌표인지 확인한다.
두 조건을 모두 만족할 경우 해당 좌표에 대한 방문 리스트를 체크하고 해당 좌표를 큐에 삽입한다.
또한 해당 좌표까지 이동한 거리를 직전 좌표까지 이동한 거리 + 1한 값으로 업데이트한다.
(4) 출력하기
BFS(1, 1)
print(A[N][M])
도착 지점 좌표까지의 거리를 출력한다.
✅ 정답 확인

포스팅한 내용에 대한 조언/지적/피드백 모두 환영입니다!
읽어주셔서 감사합니다^.^
'Algorithm > Baekjoon' 카테고리의 다른 글
[해시] 백준 #20920 영단어 암기는 괴로워 - Python (0) | 2024.02.20 |
---|---|
[BFS] 백준 #1167 트리의 지름 구하기 - Python (1) | 2023.10.10 |
[DFS/BFS] 백준 #1260 DFS와 BFS 프로그램 - Python (0) | 2023.10.09 |
[DFS] 백준 #13023 친구 관계 파악하기 - Python (2) | 2023.10.09 |
[DFS] 백준 #2023 신기한 소수 찾기 - Python (1) | 2023.10.09 |
📚 문제
링크: https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
💡 접근법
미로에서 서로 인접한 칸으로만 이동하여 최단 거리를 구해야 하므로 BFS를 이용해야 한다.
BFS란?
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
해당 문제의 키 포인트는 2가지이다.
1. 미로 문제에서 이동을 조작하고 싶을 때 x, y에 대한 변화량을 나타내는 dx, dy를 선언한다.
문제에서 정의한 움직임은 총 4가지로, 상, 하, 좌, 우이다. 이를 dx와 dy로 나타내면 다음과 같다.
dx = [0, 0, 1, -1], dy = [1, -1, 0, 0]
또한 움직임을 적용할 때 미로의 범위를 확인해야 한다. 즉, 미로를 벗어나면 안 된다.
따라서 특정 좌표에서 미로 범위에 대한 조건문을 수행해야 한다.
2. 인접 리스트의 값 자체를 이동 횟수로 저장하면서 탐색을 진행한다. (DP와 유사한 방식)
(nx, ny) 좌표에 대하여 visited[nx][ny] == False and A[nx][ny] == 1을 만족한다면 이는 방문한 적이 없는 노드임을 뜻한다. 따라서 (x, y) 값에 +1을 한 값은 현재까지 이동한 거리(깊이)가 된다.
💻 코드
1) 전체 코드
import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
A = [[]]
visited = [[False] * (M+1) for _ in range(N+1)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
for _ in range(N):
temp = list(map(int, sys.stdin.readline().strip()))
temp.insert(0, 0)
A.append(temp)
def BFS(v, w):
queue = deque()
queue.append((v, w))
visited[v][w] = True
while queue:
node = queue.popleft()
for k in range(4):
nx = node[0] + dx[k]
ny = node[1] + dy[k]
if N >= nx > 0 and M >= ny > 0:
if not visited[nx][ny] and A[nx][ny] == 1:
visited[nx][ny] = True
queue.append((nx, ny))
A[nx][ny] = A[node[0]][node[1]] + 1
BFS(1, 1)
print(A[N][M])
2) 해설
(1) 패키지 Import
import sys
from collections import deque
파이썬 내장 함수인 input()보다 빠르게 값을 입력받기 위해 sys 라이브러리, 큐를 사용하기 위해 collections.deque 모듈을 임포트한다.
(2) 입력받기
N, M = map(int, sys.stdin.readline().split())
A = [[]]
visited = [[False] * (M+1) for _ in range(N+1)]
for _ in range(N):
temp = list(map(int, sys.stdin.readline().strip()))
temp.insert(0, 0)
A.append(temp)
도착 위치 좌표(N, M)를 입력받고, 인접 리스트(A)와 방문 리스트(visited)를 초기화한다.
for문을 순회하면서 인접 리스트, 즉 미로를 생성한다.
(3) BFS 구현
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def BFS(v, w):
queue = deque()
queue.append((v, w))
visited[v][w] = True
while queue:
node = queue.popleft()
for k in range(4):
nx = node[0] + dx[k]
ny = node[1] + dy[k]
if N >= nx > 0 and M >= ny > 0:
if not visited[nx][ny] and A[nx][ny] == 1:
visited[nx][ny] = True
queue.append((nx, ny))
A[nx][ny] = A[node[0]][node[1]] + 1
deque()를 생성하고 현재 좌표를 튜플로 큐에 삽입한다.
현재 좌표에 대해 방문 리스트를 체크하고 큐가 빌 때까지 while 문을 수행하기 시작한다.
큐에서 노드를 꺼내고 현재 노드에서 인접한 칸을 상하좌우로 탐색한다.
이때 움직임을 적용한 좌표가 1) 미로의 범위를 벗어나지 않는지 2) 방문한 적이 없는 좌표인지 확인한다.
두 조건을 모두 만족할 경우 해당 좌표에 대한 방문 리스트를 체크하고 해당 좌표를 큐에 삽입한다.
또한 해당 좌표까지 이동한 거리를 직전 좌표까지 이동한 거리 + 1한 값으로 업데이트한다.
(4) 출력하기
BFS(1, 1)
print(A[N][M])
도착 지점 좌표까지의 거리를 출력한다.
✅ 정답 확인

포스팅한 내용에 대한 조언/지적/피드백 모두 환영입니다!
읽어주셔서 감사합니다^.^
'Algorithm > Baekjoon' 카테고리의 다른 글
[해시] 백준 #20920 영단어 암기는 괴로워 - Python (0) | 2024.02.20 |
---|---|
[BFS] 백준 #1167 트리의 지름 구하기 - Python (1) | 2023.10.10 |
[DFS/BFS] 백준 #1260 DFS와 BFS 프로그램 - Python (0) | 2023.10.09 |
[DFS] 백준 #13023 친구 관계 파악하기 - Python (2) | 2023.10.09 |
[DFS] 백준 #2023 신기한 소수 찾기 - Python (1) | 2023.10.09 |