[백준 2178] 미로 탐색

문제 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

출처 : https://j-remind.tistory.com/52

▶ 코드 ( 큐 ver. )

■큐에 중복 원소(r, l)이 있는지 검사 안해서 시간초과

from collections import deque

n, m = map(int, input().split()) # n:세로, m:가로
myMap = []

for _ in range(n):
    inputString = input()
    myMap.append(list(map(int, inputString)))
#print(myMap)
    
dx = [1,-1,0,0]
dy = [0,0,1,-1]

visited = [[0]*m for _ in range(n)]
depth = [[0]*m for _ in range(n)]
    
def isInGraph(r, l): # r: 세로, l: 가로
    if r < 0 or r >= n or l < 0 or l >= m:
        return False
    return True
    
def bfs(r, l):
    
    visited[r][l] = 1
    depth[r][l] = 1 # 처음 시작은 1

    # 큐 이용
    dq = deque()
    dq.append([r,l]) # BFS로 사용될 큐 

    while dq:
        [r, l] = dq.popleft()
        visited[r][l] = 1
    
        #상하좌우 탐색
        tx = 0
        tx = 0
        for i in range(4):
              tx = r + dx[i]
              ty = l + dy[i]

              if isInGraph(tx, ty):
                  if visited[tx][ty] == 0 and myMap[tx][ty] == 1:
                      dq.append([tx,ty])
                      depth[tx][ty] = depth[r][l] + 1

    
        '''
        # 재귀 이용 
        if isInGraph(tx, ty):
            if visited[tx][ty] == 0 and myMap[tx][ty] == 1:
                bfs(tx, ty, depth_list[r][l]+1)
        '''

bfs(0,0) # 첫위치 에서 시작 

print(depth[n-1][m-1])

 

▶ 코드 ( 큐 ver. )

■큐에 중복 원소(r, l)이 있는지 검사 추가. 정답

from collections import deque

n, m = map(int, input().split()) # n:세로, m:가로
myMap = []

for _ in range(n):
    inputString = input()
    myMap.append(list(map(int, inputString)))
#print(myMap)
    
dx = [1,-1,0,0]
dy = [0,0,1,-1]

visited = [[0]*m for _ in range(n)]
depth = [[0]*m for _ in range(n)]
    
def isInGraph(r, l): # r: 세로, l: 가로
    if r < 0 or r >= n or l < 0 or l >= m:
        return False
    return True
    
def bfs(r, l):
    
    visited[r][l] = 1
    depth[r][l] = 1 # 처음 시작은 1

    # 큐 이용
    dq = deque()
    dq.append([r,l]) # BFS로 사용될 큐 

    while dq:
        [r, l] = dq.popleft()
        visited[r][l] = 1
    
        #상하좌우 탐색
        tx = 0
        tx = 0
        for i in range(4):
              tx = r + dx[i]
              ty = l + dy[i]

              if isInGraph(tx, ty):
                  if visited[tx][ty] == 0 and myMap[tx][ty] == 1 and [tx,ty] not in dq:
                      dq.append([tx,ty])
                      depth[tx][ty] = depth[r][l] + 1

    
        '''
        # 재귀 이용 
        if isInGraph(tx, ty):
            if visited[tx][ty] == 0 and myMap[tx][ty] == 1:
                bfs(tx, ty, depth_list[r][l]+1)
        '''

bfs(0,0) # 첫위치 에서 시작 

print(depth[n-1][m-1])

 

※ python3로 채점해야 메모리초과 X

※ 원배열이 모두 1이므로, visited를 통해 방문처리 해줘야 한다.

※ 큐에서 뺀 원소가 큐에 있는지 검사 추가 해줘야 시간초과 X 되는 문제