728x90
반응형
<문제 링크>
https://www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
<풀이>
너비 우선 탐색(BFS)를 이용하여 미로를 빠져 나가기 위한 최소 이동 횟수를 구하는 문제이다.
그래서 BFS를 위해 방문 정보를 담는 visited와 queue는 무조건 있어야 한다.
blocks을 초기화 할 때 좌우상하 이동을 위해 padding을 주었고(Index Out 에러 방지) blocks에 칸이 1인지 0인지를 입력 받은 후에
BFS 메소드에 (N, M, blocks. queue, visited)를 넘겨 주어 출구인 visited[N][M]가 True될 때까지 반복문을 돌려준다.
queue를 기준으로 다음 좌표들을 모아 next_research에 담아 주고
이를 다시 queue에 삽입해 [N][M]을 가장 먼저 방문할 때까지 너비 우선 탐색을 진행한다.
<코드>
(N, M): 미로 탈출구 좌표
blocks: 미로 블록 정보
queue: 너비 우선 탐색 큐
visited: 방문 정보
next_research: 다음으로 탐색할 위치 정보들
count: 최소 이동 횟수(정답)
def BFS(N, M, blocks, queue, visited):
count = 0 # 이동 횟수
while not visited[N][M] and queue:
next_research = [] # 다음으로 탐색할 위치 정보
count += 1 # 횟수++
for pos in queue:
i = pos[0]
j = pos[1]
# 방문 하지 않은 장소라면
if not visited[i][j]:
# 방문 체크
visited[i][j] = True
# 4 방향 중 어디로 갈 지 체크
if blocks[i+1][j] == 1 and not visited[i+1][j]:
next_research.append([i+1, j])
if blocks[i][j+1] == 1 and not visited[i][j+1]:
next_research.append([i, j+1])
if blocks[i][j-1] == 1 and not visited[i][j-1]:
next_research.append([i, j-1])
if blocks[i-1][j] == 1 and not visited[i-1][j]:
next_research.append([i-1, j])
# 너비 우선 탐색 갱신
queue = next_research.copy()
return count
if __name__ == "__main__":
N, M = map(int, input().split()) # (N, M)
blocks = [[0 for _ in range(M+2)] for _ in range(N+2)] # 미로 블록 정보
queue = [[1, 1]] # BFS 큐
visited = [[False for _ in range(M+2)] for _ in range(N+2)] # 방문 여부
# input
for i in range(1, N + 1):
blocks[i] = list(map(int, list(input())))
blocks[i].insert(0, 0)
blocks[i].insert(M+1, 0)
print(BFS(N, M, blocks, queue, visited))
728x90
반응형
'~2023' 카테고리의 다른 글
| [Python] 백준 2156번 문제, 포도주 시식 (0) | 2021.07.12 |
|---|---|
| [Python] 백준 12865번 문제, 평범한 배낭 (0) | 2021.07.04 |
| [JAVA] 백준 17478번 문제, 재귀함수가 뭔가요? (0) | 2021.07.04 |
| [JAVA/PYTHON] 백준 1158번 문제, 요세푸스 문제 (0) | 2021.06.26 |
| [JAVA] 백준 2822번 문제, 점수 계산 (0) | 2021.06.25 |
