[SWEA 4871번 문제]
def dfs(start,end):
stack = [start] # stack 초기화
visited = [False] * (V+1) # 방문 여부를 검사
while stack : # stack이 빌때까지
v = stack.pop() # 시작 정점을 stack에서 꺼내고 다른 변수에 저장
visited[v] = True # 방문했다는 것을 표시
for w in range(V+1):
if visited[w] == 0 : # 방문하지 않았다면
if G[v][w] == 1: # 간선이 있다면
stack.append(w) # 연결되어 있으므로 stack에 추가
return visited[end] # True 면 경로가 있는 것
T = int(input()) # 테스트 케이스 수
for tc in range(1,T+1):
V,E = map(int,input().split()) # V = 노드 수 , E = 간선 수
G = [[0] * (V + 1) for _ in range(V + 1)]
for i in range(E): # G에 연결된 정점 표시해주기
s,e = map(int,input().split())
G[s][e] = 1
S,g = map(int,input().split()) # 확인할 시작 노드 와 끝 노드 입력 받기
if dfs(S,g):
print(f'#{tc} {1}')
else :
print(f'#{tc} {0}')테스트 케이스가 처음에 주어지고,노드 수와 간선수가 주어진다.
1부터 V 까지의 각 경로를 표기해주기 위해, V+1개의 0으로 구성된 이차원 배열 G를 생성했다.
(정점이 1부터 시작하므로 인덱스값을 일치시키기 위해 1개 더 추가)
각 정점의 시작점과 연결점을 입력받고 G에 연결된 부분은 1로 초기화시켜주었다.
그리고 우리가 최종 확인할 시작 노드와 끝 노드가 연결되었는지 알아보기 위해 먼저, 시작 노드와 끝 노드 값을 입력 받고,이를 dfs 라는 함수로 확인하였다.
dfs 함수는 먼저 stack 이라는 리스트에 시작값을 넣어주었고, 방문 여부를 검사하기 위해 V+1 개만큼의 False로 이뤄진 배열을 생성했다.
stack이라는 리스트가 비어있을 때 까지 반복문을 순환한다.
v 는 stack의 값을 pop 한 것을 저장시켜주었고, v 값이 visited 에 들어온다면 방문했다는 의미로 True 값으로 바꿔주었다.
주어진 정점이 다른 정점과 연결되어있는지 확인하기 위해, for문 안에 두번의 if문을 조건으로 주었는데, 처음은 방문하지 않은 노드라면 다음 if문으로 진행하게 했다. 방문한 노드라면 이미 visited 에 True 값일 것이므로 또 다시 확인할 필요가 없다.
다음 if문으로 들어온 값이 G에 저장된 값을 통해 간선이 있는지 확인하고, 간선이 있다면 stack에 append 한다.
이를 계속 반복하면 stack이 비어있을 때 반복문이 종료되고, dfs에 주어진 start 인자값과 end 인자값이 연결되어 있으면 1을 return 하고 그렇지 않으면 0 을 리턴한다.
그리고 출력조건에 맞게 출력해주면 된다.
