📌풀이
내가 쓴 풀이(성공)
- 역방향으로 탐색(도착점에서 시작점으로)
- 정방향으로 하여도 상관 없음
- edge 들이 저장되어 있는 input 값을 받아오고, 각 값들은 시작점, 끝점의 쌍이 계속 진행되는 형태임을 고려
connected에 key를 도착점으로 하고, value에 시작점 추가- 정방향으로 하고 싶은 경우, key를 시작점으로, value에 도착점 추가
- 결과를 나타낼 변수
res - DFS를 위한 스택 생성 후, 도착점
99을 집어넣음- 시작점부터 보는 경우,
0을 넣음
- 시작점부터 보는 경우,
- 스택이 비워질때까지 진행
- 스택에서 꺼낸 노드는 방문처리
- 현재 꺼내진 노드의 인접 노드들을 탐색하고, 해당 노드가 방문하지 않았거나, 스택에 없는 경우 스택에 추가
- 출발점이 스택에 들어가는 순간 while문 종료(방문 예정이므로)
- 출발점을 기준으로 하였다면, 도착점이 스택에 들어가는 순간
from collections import defaultdict
for _ in range(1, 11):
tc, e = map(int, input().split())
visited = defaultdict(int) # 방문 여부 확인용 딕셔너리
connected = defaultdict(list) # 노드 간 연결용 딕셔너리
edges = list(map(int, input().split()))
for i in range(e):
start, end = edges[2*i], edges[2*i+1]
connected[end].append(start) # 도착점을 기준으로 딕셔너리 구현, 역순으로 탐색
res = 0 # 결과 값 초기화
stack = [99] # 도착점에서부터 시작점으로 탐색
while stack :
# 스택에서 꺼낸 노드는 방문처리
current = stack.pop()
visited[current] = 1
for v in connected[current] : # 연결된 노드들 확인
# 노드를 방문하지 않았거나, 스택에 들어있지 않은 경우, 스택에 추가
if not visited[v] and v not in stack :
stack.append(v)
# 시작점이 방문 예정인 경우, while문을 마침
if 0 in stack :
res = 1
break
print(f'#{tc} {res}')Recursion을 활용한 DFS
# 정방향 탐색 기준
for _ in range(1, 11):
tc, e = map(int, input().split())
visited = [0] * 100 # 방문 여부 확인용 리스트
connected = [[] for _ in range(100)] # 노드 간 연결용 리스트
edges = list(map(int, input().split()))
for i in range(e):
start, end = edges[2*i], edges[2*i+1]
connected[start].append(end) # 시작점을 기준으로 딕셔너리 구현
def dfs(s):
visited[s] = 1 # 방문표시
for v in connected[s] :
if not visited[v] : # 인접 노드 중 방문하지 않은 경우, dfs
dfs(v)
dfs(0) # 시작점인 0을 기준으로 dfs
print(f'#{tc} {visited[-1]}') #도착점의 방문 여부 확인📌후기
노드의 갯수가 많지 않은 경우도 있어서, defaultdict를 활용하는 것이 더 효율적이라고 생각하였다. 하지만, 다른 사람들의 코드를 보니 리스트로 구현한 것이 내가 구현한 방식보다 속도가 더 빠르고 메모리도 작다는 것을 알 수 있었다. 리스트를 활용해서 하는 방법도 많이 생각을 해봐야겠다!
재귀를 활용해서 dfs를 짜는 법이 익숙하지 않은데, 백트래킹을 활용할 수 있는 좋은 방법이라고 하니 다른 예제에서 더 써봐야겠다!
Growing Developer