[CodingTest] BOJ13023 ABCDE ( DFS ) With 파이썬

13023번: ABCDE

 

◎ 문제풀이 

 

그래프를 탐색하여 A ⇢ B ⇢ C ⇢ D ⇢ E 경우가 있는지 탐색해야 한다. 그래프의 탐색은 DFS와 BFS가 있다. 참조의 참조를 하는 문제이므로 DFS가 적절하다. DFS는 STACK으로 구현된다. STACK은 '기억' 기능이 있어서 함수가 호출되면 STACK 영역에 차례대로 쌓여 호출된 순서가 기억된다. 그러므로 DFS는 STACK을 직접 구현하지 않아도 재귀호출를 사용하면 된다.

 

위 문제를 풀면서 놓친 부분은 3가지가 있다.

 

1) 방문이력테이블이 필요하다는 생각 X

깊이탐색은 count가 4일때까지 이루어진다. 여기에는 재방문이 포함될 수 있다. 그러므로 재방문을 제외해야 한다.

 

2) 방문이력테이블을 원복해야 한다는 생각X

DFS는 모든 노드에서 시작되어야 한다. 한 노드에서 시작된 DFS가 변경해놓은 방문이력테이블은 다른 노드를 위해 원복해놓아야 한다. 

3) 양방향 관계임을 인지 X

친구 사이이므로 단방향 관계가 아니다. 

 

 

◎ 코드 

import sys
input= sys.stdin.readline

n,m = map(int, input().split())
graph = [[] for _ in range(n) ]
visited = [False] * n
flag = False

# 그래프 초기화
for _ in range(m) :
  a,b = map(int,input().split())
  graph[a].append(b) #양방향 관계!
  graph[b].append(a)

# DFS 알고리즘
def dfs(index, count) :
  visited[index] = True #방문이력 True
  if count == 4 : return True # A-B-C-D-E 발견!
  for i in graph[index] : # 다른 노드로 이동
    if visited[i] : continue # 방문한 노드제외
    if dfs(i,count+1) : return True # 발견하면 탐색종료
    visited[i] = False # 발견못하면 원복

#DFS 탐색시작
for i in range(n) :
  if dfs(i,0) : # 탐색성공하면 반복종료
    flag = True
    break
  visited[i] = False #탐색실패하면 원복

#출력
if flag : print(1)
else : print(0)