T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
# 출발 노드(S)에서 갈 수 있는 번호들을 하나씩 따라가며 방문 표시를 하다가,
# 도착 노드(G)에 한 번이라도 발을 들이게 되는지 확인하는 것이 핵심입니다.
# 한 노드에서 갈 수 있는 장소들을 모두 모아두고, 그 곳에서 도착노드까지 갈 수 있는지?
for test_case in range(1, T + 1):
# ///////////////////////////////////////////////////////////////////////////////////
v, e = map(int, input().split()) # v: 노드 갯수 e: 간선 갯수
# node_list = [[]] * v 이것도 shallow copy
node_list = [[] for _ in range (v+1)]
# 노드 하나에서 여러 노드로 갈 수도 있으므로
# 노드 갯수+1만큼 리스트 만듦 (index 관리의 용이성을 위해 index 0은 비워두기로 하고 노드 수를 그대로 index로 이용)
for _ in range (e):
a, b = map(int, input().split())
node_list[a].append(b)
s, g = map(int, input().split()) # s: 출발, g: 도착
stack = [s] # 사용자님의 'check'와 같은 역할
visited = [False] * (v + 1)
visited[s] = True
answer = 0
while stack: # 가볼 곳이 있는 동안 무한 반복!
now = stack.pop()
if now == g: # 도착!
answer = 1
break
else:
for next_node in node_list[now]: # 현재 노드의 친구들 확인
if not visited[next_node]: # 안 가본 곳만 골라서
visited[next_node] = True # 방문 도장 찍고
stack.append(next_node) # 다음에 가보려고 목록(stack)에 넣기
print(f"#{test_case} {answer}")
# ///////////////////////////////////////////////////////////////////////////////////
'''
v, e = map(int, input().split()) # v: 노드 e: 간선
node_dict = {}
visited = []
answer = 0
for _ in range (e):
a, b = map(int, input().split()) # dict에 간선 시작점을 key로, 끝점을 value로 저장
node_dict[a]=b
s, g = map(int, input().split()) # s: 출발, g: 도착
n = s # 현재 노드 값 저장 변수
#
visited.append(n) # 첫 시작
while len(visted) != 0:
if n in node_dict:
visited.append(node_dict[n])
del node_dict[n]
n = data_stack[-1]
else:
if node_dict[n] in node_dict.values():
n =
#이 문제에서는 dict 쓰지 말자'''
''' n = s # 현재 노드 값 저장 변수
# v와 w대신 변수 하나 쓰고 인접 노드 리스트 pop 하면?
visited.append(n)
check.append(n)
#조건이 while check임!!! stack에 갈 곳이 남아 있을 때....
len(node_list[n]) !=0: # 그 노드에서 갈 수 있는 다음 노드 찾기
for i in range (len(node_list[n])):
new_node = node_list[n][i]
if new_node == (g): # 다음 노드가 목표 노드일 때
answer = 1
break
else: #다음 노드가 목표 노드가 아닐 때
if new_node in visited: #이미 방문한 곳이면 그냥 넘어가기
pass
else: #다음 노드가 방문하지 않은 곳이면
if len(node_list[new_node]) == 0: # 만약 다음 노드에서 갈 수 있는 곳이 없으면
visited.append(new_node) # 방문 했다고만 체크
else: # 다음 노드가 방문했던 적도 없고, 그 곳에서 갈 수 있는 곳도 있으면
visited.append(new_node) # 방문 체크
check.append(new_node) # 분기 체크
n = new_node # n 변경
else: # 그 노드가 비었으면 다시 역으로 가서 노드에서 찾기
if len(check) !=0:
check.pop()
else:
answer = 0
break
print (answer)'''내가 다시 짠 코드
- stack (할 일 리스트)에 첫 노드 넣고 시작
- 첫 노드는 방문 아직 안 한 상태로! 그래야 처음 루프 들어갔을 때 stack에 갈 수 있는 곳 리스트가 추가 됨
- now는 while문 안에서 정의되며 이 경우 now가 목표 노드인 경우의 수와, now가 아직 방문하지 않은 노드인 경우의 수만 고려하면 나머지 경우는 그냥 now = stack.pop()으로 해결 가능 → now = stack.pop()을 while문 가장 앞으로 빼는 게 핵심
T = int(input())
for test_case in range(1, T + 1):
v, e = map(int, input().split()) # v: 노드 갯수 e: 간선 갯수
# node_list = [[]] * v 이것도 shallow copy
node_list = [[] for _ in range (v+1)]
# 노드 하나에서 여러 노드로 갈 수도 있으므로
# 노드 갯수+1만큼 리스트 만듦 (index 관리의 용이성을 위해 index 0은 비워두기로 하고 노드 수를 그대로 index로 이용)
for _ in range (e):
a, b = map(int, input().split())
node_list[a].append(b)
s, g = map(int, input().split()) # s: 출발, g: 도착
stack = [s] # 사용자님의 'check'와 같은 역할
visited = [False] * (v + 1)
#visited[s] = True
answer = 0
while stack:
now = stack.pop()
#print(now)
if now == g:
visited[now] = True
answer = 1
break
else:
if not visited[now]:
visited[now] = True # 위에다가 넣으면 if not visited의 경우가 사라짐
stack.extend(node_list[now])
#print (node_list[now])
print (f'#{test_case} {answer}')```