[백준][파이썬] 11403번: 경로찾기 BFS문제

BFS 문제인 이유:

인접 행렬들을 하나씩 True 해나가는 과정이기떄문.

사실 DFS로 풀어도 될것같긴하다

어차피 False처리를 계속 해주기때문에 메모리나 시간에 있어서도 비슷할것 같다는 생각이 든다.

핵심은 

1. 초기값 dfs안에 한번에 stack변수에 저장(배추문제에서도 했다.)

2. collection 이용하여 시간단축

복잡하지 않은 문제였다.

import collections
num = int(input())
lit =[]
visited = [[False for i in range(num)] for j in range(num)]
for i in range(num):
    t = list(map(int,input().split()))
    lit.append(t)

def dfs(stack):
    stack = stack
    for i in range(num):
        for j in range(num):
            if lit[i][j] == 1:
                visited[i][j] =True
                stack.append([i,j])
    while stack:
        x = stack[0][0]
        y = stack[0][1]
        stack.popleft()
        for i in range(num):
            if lit[y][i] == 1 and lit[x][i] == 0 and visited[x][i] == False:
                stack.append([x,i])
                lit[x][i] = 1
                visited[x][i] = True

    return



t = collections.deque()
dfs(t)
for i in range(num):
    print(*lit[i])