[BOJ 11403] 경로 찾기

Depth First Search

[BOJ 11403] 경로 찾기

문제

구조화

• 초기 접근
  • 입력 배열의 I,J의 값이 1인 경우 i->j로 가는 인접 행렬 생성
  • 각 노드 별 DFS 탐색
  • 탐색 결과 출력
• 반례 발생
  • 61%에서 오류 발생
  • 원인은 DFS 탐색과 동시에 현재 노드에서 방문 처리를 진행했기 때문에 발생.
  • 즉, 현재 노드가 방문처리가 된다는 뜻은, 현재 노드로 돌아올 수 있음을 의미하나, 만약 이후 인접행렬에서 이러한 케이스가 존재하지 않을 경우 오류가 발생
  • 방문 처리를 현재 노드가 아닌 연결된 다음 노드를 갱신해줌으로써 해결

해답

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n=int(input())
data= []
for i in range(n):
    data.append(list(map(int,input().split())))

graph = [[] for i in range(n+1)]
for i in range(len(data)):
    for j in range(len(data[i])):
        if data[i][j]==1:
            graph[i].append(j)

def dfs(node):
    for nxt in graph[node]:
        if state[nxt]==0: 
            state[nxt]=1
            dfs(nxt)
            
for i in range(n):
    state = [0 for i in range(n+1)]
    dfs(i)
    print(' '.join(map(str, state[:n])))