문제설명
- 동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혔습니다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 합니다.
- 동빈이의 위치는 (1,1)이며 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있습니다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있습니다. 미로는 반드시 탈출할 수 있는 형태로 제시됩니다.
- 이 때 동빈이가 탈출하기 위해 움직여야하는 최소 칸의 개수를 구하세요. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산합니다.
입력조건
- 첫째줄에 두 정수 N,M(4<=N, M<=200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어집니다. 각각의 수들은 공백없이 붙어서 입력으로 제시됩니다. 또한 시작 칸과 마지막 칸은 항상 1입니다.
출력조건
- 첫째 줄에 최소 이동 칸의 개수를 출력합니다.
입력예시
5 6
101010
111111
000001
111111
111111출력예시
10내가짠코드
# N, M을 공백 기준으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
flag = True # left first if True(n>m), else down first(n<m)
if n < m:
flag = False
i, j = 0, 0 # initial position\
cnt = 0
def func(i, j, cnt):
print("HEY", i, j)
if graph[i][j] == 1:
graph[i][j] = True
cnt += 1
if flag == True:
if i < m:
result = func(i + 1, j, cnt)
if result == False:
if j < n:
func(i, j + 1, cnt)
else:
func(i, j + 1, cnt)
else:
print("INIT", i, j, n, m)
if j < n:
result = func(i, j+1, cnt)
print(i, j, result)
if result == False:
if i < m:
func(i+1, j, cnt)
else:
func(i + 1, j, cnt)
return True
else:
return False
func(i, j, cnt)bfs를 활용해서 다시 짠 코드
from collections import deque
# N, M을 공백 기준으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 이동할 네 가지 방향 정의(상하좌우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
x, y = queue.popleft()
if x == n - 1 and y == m - 1:
return graph[x][y]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx > n-1 or ny > m-1:
continue
if graph[nx][ny] == 0:
continue
if graph[nx][ny] == 1:
queue.append((nx, ny))
graph[nx][ny] = graph[x][y] + 1
print(bfs(0,0)) # 10정답코드
from collections import deque
# N, M을 공백 기준으로 구분하여 입력받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append((x, y))
# 큐가 빌 때까지 반복하기
while queue:
x, y = queue.popleft()
# 현재 위치에서 4가지 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 미로 찾기 공간을 벗어난 경우 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
# 벽인 경우 무시
if graph[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 경로 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
# 가장 오른쪽 아래의 최단 거리 반환
return graph[n-1][m-1]
# BFS를 수행한 결과 출력
print(bfs(0,0))해설
이 문제에서는 n-1, m-1에 도달하면 바로 종료를 시키도록 while 루프 안에 조건문을 걸어 줄 수 있다. 최악의 경우 이 조건문을 수행하는 것은 비용이 되지만, 빠르게 목적지에 도달한다면 불필요한 연산을 피할 수도 있다. 최대한 불필요한 연산을 피하기 위해서는 아래 로직을 추가할 수 있다.
n이 m보다 작다면, 위 아래를 먼저 방문하도록 dx = [-1, 1, 0, 0], dy = [0, 0,-1, 1]
n이 m보다 크다면, 좌 우를 먼저 방문하도록 dx = [0, 0, -1, 1], dy = [-1, 1, 0, 0] 할 수 있을 것이다.
yozzum