4871_그래프_경로 문제와 거의 같은 문제 반복문 통한 장부 정리 (to_do)로 풂
else에서도 now 당연히 갱신해야 그냥 to_do.pop()이 아니라, now = to_do.pop()으로 해야 → 걍 아래 개선책처럼 짜자 깊이 우선이다 보니 이미 할 일 리스트의 맨 끝에 있는 쪽으로 now가 바뀌면, 더 깊이 들어가지 옆에 있는 애들은 그냥 넘어감 ex) 0 - 1, 2, 3 - 3 - 7… now = 0일 때 1, 2, 3 방문 리스트에 들어감. 3부터 pop하므로 3 - 7 경로 따라 들어감 → 1, 2는 to_do에만 있고 아직 방문 안 함. 즉 3에서 시작한 모든 가지 방문했을 때 (else 경우) 1, 2도 탐색 되게끔 now 갱신해야
for test_case in range(1, 11):
# ///////////////////////////////////////////////////////////////////////////////////
_, n = map(int, input().split())
edge_list =[[] for _ in range (100)] # Edge -> 간선. 노드 갯수만큼 만들고 index를 시작 노드로 활용
temp_list = list(map(int,input().split()))
index = 0
for i in range (2*n): # 들어오는 간선 정보를 edge_list에 넣어줌
# index = 시작 노드, edge_list[index] = 갈 수 있는 노드
if i % 2 == 0:
index = temp_list[i]
else:
edge_list[index].append(temp_list[i])
visited = [False] * (100) # 노드 수는 0-99 -> 100개
to_do = [0] # 할 일 적어두는 장부로 활용, 기본은 시작 노드 들어있음
s = 0
g = 99 # 시작 / 끝 노드는 0, 99로 고정
now = 0 # 현재 위치
answer = 0
while to_do: # 할 일 리스트가 있으면 (문법 상 리스트 이름만 쓰고 굳이 len 함수 안 써도, 비면 나온다)
if now == g: # 지금 목표 노드에 와 있으면
visited[now] = True
answer = 1
break
else: # 지금 위치가 목표 노드가 아니면
if not visited[now]: # 지금 위치가 방문했던 노드가 아니면
# 중요 문법 - T/F 리스트니까 if not visited[now] 이렇게 바로 쓸 수 있다 (~in ~같은거 필요 없음)
# 이거 하나로 할 일 리스트만 보고 작동하게 되어 여러 분기 만들 필요가 없음!
# 다음에 방문할 곳이 없어도 빈 리스트가 추가되고 현 위치 pop되므로 상관 없음! 최고다
visited[now] = True
# to_do.pop()
# 현재 위치 먼저 pop하면 처음 시작 때 다음 리스트 추가 전 pop 되어서 땡
to_do.extend(edge_list[now]) # 할 일 리스트에 다음에 갈 곳 추가
# append 아니고 extend임에 주의! (list 내용 풀어서 뒤에 추가)
now = to_do.pop() # 다음에 갈 곳 중 마지막 친구 pop 하면서 현재 위치로 갈아끼우기
else: # 지금 위치가 방문 했던 노드라면 = 더 이상 근처에 방문하지 않은 곳이 없다면
now = to_do.pop() # 할 일 리스트에서 현 위치 제거
# 그냥 to_do.pop()이면 방문한 노드일 때(else), now를 다음 할 일로 갱신이 안 됨
# case_6 값이 달라졌네 -> now 갱신을 해 줘야 돌아가다가 다른 루트로 빠져서 답을 찾을 수 있음
print (f'#{test_case} {answer}') 개선점
-
now라는 외부 변수와to_do라는 스택을 따로 관리하다 보니, 스택이 비는 시점과now를 검사하는 시점이 어긋날 위험 존재 -
now = to_do.pop()을if/else양쪽에서 중복으로 사용하고 계신데, 이 부분만 위쪽으로 합치면 훨씬 깔끔해질 것 같습니다.
Gemini의 개선책
for _ in range(1, 11):
tc_num, n = map(int, input().split())
temp_list = list(map(int, input().split()))
# 1. 인접 리스트 생성
edge_list = [[] for _ in range(100)]
for i in range(0, 2 * n, 2):
u, v = temp_list[i], temp_list[i+1]
edge_list[u].append(v)
# 2. 탐색 준비
visited = [False] * 100
to_do = [0] # 출발 노드 0을 장부에 넣고 시작
answer = 0
# 3. 탐색 시작
while to_do:
# 일단 장부에서 하나를 꺼냅니다 (중복 pop 제거)
# 여기서 방문한 노드 (위에서의 else case)도 처리 됨
# 훨씬 덜 헷갈림
now = to_do.pop()
#이러면 to_do에 든 거 없어져서 안 멈추나?
# -> 이미 while문 조건 통과해서 중간에서 멈추진 않음
# 목표 노드에 도착했으면 종료
if now == 99:
answer = 1
break
# 방문하지 않은 노드라면 방문 처리 후 갈 수 있는 곳을 장부에 추가
if not visited[now]:
visited[now] = True
# 현재 노드에서 갈 수 있는 모든 노드를 장부에 추가
to_do.extend(edge_list[now])
print(f'#{tc_num} {answer}')-
중복 코드 제거
if/else양쪽에서now = to_do.pop()을 호출하던 것을while문 최상단에서 한 번만 -
논리적 일관성 “장부(
to_do)에서 노드를 꺼낸다 → 그 노드가 목표인지 확인한다 → 방문 안 했으면 주변 노드를 장부에 넣는다”는 일직선의 흐름 -
안전성 now 변수의 선언 필요 없이,
to_do에 들어있는 값이 곧now가 되므로 데이터의 흐름이 더 명확합니다.