[BFS] 백준 - 1261번 알고스팟

BFS

벽 부시는 것을 최소화 하는 경로를 찾기 위해서 일단은 주변 방들을 탐색하면서 진행하는 것이 좋다고 판단해 BFS를 사용한다. 

 

벽 부시기 횟수 최소화 하기 위한 조건?

1인 방에 가면 벽을 부셔야 하는 횟수가 늘어나기 때문에 0인 방부터 우선으로 검사할 수 있도록 하자

• 0인 방은 일단 부시기가 안 일어나므로 Queue에서 appendLeft하여 먼저 pop 될 수 있도록 한다
• 1인 방은 부시기가 일어나므로 Queue에서 append 하여서 pop 우선순위를 뒤로 미룬다

방문 여부 체크

BFS와 Queue를 통해 가장 빠르고 부시는 수를 최소화 할 수 있는 경로로 찾아가기 때문에 한번 방문한 방을 방문처리를 하지 않는다면 다른 노드에서 다시 방문해서 속도가 떨어질 것이라 판단

visited 배열을 따로 생성하지 않고 graph에서 방문이 끝나면 1/0을 -1로 바꾸어 주는 방식을 택함

1차 코드

from collections import deque
import sys
inpurt = sys.stdin.readline

INF = int(1e9)

M, N = map(int, input().split()) # M 가로 크기 / N 세로 크기

graph = [list(map(int, input().rstrip()))for _ in range(N)]
dir_col = [1, 0, -1, 0]
dir_row = [0, 1, 0, -1]


queue = deque()
    
def miro(graph):
    
    queue.append([0, 0, 0])
    
    while len(queue) != 0:
        
        pop_room = queue.popleft()
        graph[pop_room[0]][pop_room[1]] = -1  # 문제라고 판단된 부분

        if pop_room[1] == M-1 and pop_room[0] == N-1:
            print(pop_room[2])
            return

        for i in range(0, 4):
            n_row = pop_room[0] + dir_row[i]
            n_col = pop_room[1] + dir_col[i]
            if (0<= n_col <M) and (0<= n_row <N) and graph[n_row][n_col] != -1:
                if graph[n_row][n_col] == 1:
                    queue.append([n_row, n_col, pop_room[2]+1]) 
                elif graph[n_row][n_col] == 0:
                    queue.appendleft([n_row, n_col, pop_room[2]])


miro(graph)

문제점

시간초과

큐에서 꺼낼 때만 visited 처리를 해주는 것이 노드들의 방문수를 증가시키는 것이라 생각하여 코드를 아래와 같이 큐에 넣을 때 visited로 전환하는 방식으로 처리

 

최종 코드

from collections import deque
import sys
inpurt = sys.stdin.readline

INF = int(1e9)

M, N = map(int, input().split()) # M 가로 크기 / N 세로 크기

graph = [list(map(int, input().rstrip()))for _ in range(N)]
dir_col = [1, 0, -1, 0]
dir_row = [0, 1, 0, -1]


queue = deque()
    
def miro(graph):
    
    queue.append([0, 0, 0])
    
    while len(queue) != 0:
        
        pop_room = queue.popleft()
        

        if pop_room[1] == M-1 and pop_room[0] == N-1:
            print(pop_room[2])
            return

        for i in range(0, 4):
            n_row = pop_room[0] + dir_row[i]
            n_col = pop_room[1] + dir_col[i]
            if (0<= n_col <M) and (0<= n_row <N) and graph[n_row][n_col] != -1:
                if graph[n_row][n_col] == 1:
                    graph[n_row][n_col] = -1  # 큐에 집어 넣을 때 방문 처리 진행
                    queue.append([n_row, n_col, pop_room[2]+1]) 
                elif graph[n_row][n_col] == 0:
                    graph[n_row][n_col] = -1 # 큐에 집어 넣을 때 방문 처리 진행
                    queue.appendleft([n_row, n_col, pop_room[2]])


miro(graph)