[BOJ:9327] 상근이의 여행

문제

https://www.acmicpc.net/problem/9372

[

9372번: 상근이의 여행

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가

www.acmicpc.net

](https://www.acmicpc.net/problem/9372)

문제해결방법

• 최소 방문은 항상 연결된 그래프이기 때문에 방문한 곳을 또 방문하지 않고 그대로 이어진 길을 모두 따라서 방문하면 된다. 근데 이렇게 하면 사실 전체 국가수에서 -1을 한 값이다.
• 그래도 DFS로 한번 풀어 보았다.
• 문제에 주어진 첫 번째 테스트 케이스에 대한 그림
• 그래프 연결상태
  
• main함수에서 DFS(1,0)을 호출했을 때 DFS(1,0)의 스택프레임에서 cur는 1, answer는 0이고 방문하지 않고 1과 연결된 2노드를 방문하기 위해 DFS(2,0+1)을 호출한다. 여기서 +1은 비행기 탑승횟수를 증가하는 것이다.
• DFS(2,1)의 스택프레임이 생성되고 여기서 cur는 2, answer는 1이다. 다시 2와 연결되어있고 방문하지 않은 3노드를 방문한다.
• DFS(3,2)의 스택프레임이 생성되고 여기서 cur는 3 answer는 2가 된다. 3과 연결되어 있고 방문하지 않은 노드는 없으므로 return하여 DFS(3,2)를 호출한 DFS(2,1)로 돌아가고 이때 자신의 stackframe에서의 answer(2)를 반환한다.
• 그러면 DFS(2,1)에서 반환받은 DFS(3,2)자리는 2라는 값으로 바뀌고 DFS(2,1)의 스택프레임에 다시 answer에 2를 저장한다. 그리고 answer(2)를 반환한다.
• DFS(2,1)에서 DFS(3,2)를 수행하고 돌아온 후에 asnwer = 2이고 다시 이를 DFS(1,0)으로 반환한다. DFS(1,0)에서 DFS(2,1)에서 반환 받은 값을 다시 DFS(1,0)의 스택프레임의 answer에 저장 이제 DFS(1,0)의 stackframe에서의 answer는 2가된다. 다시 이answer를 main으로 반환하여 main의 answer에 저장한다.

 

 

 

 

 

 

코드

• 첫 번째 풀이

import sys

n = int(sys.stdin.readline().rstrip())

for i in range(n):  
countryOfNum, flightOfNum = map(int, sys.stdin.readline().rstrip().split())

for j in range(flightOfNum):
    a, b = map(int, sys.stdin.readline().rstrip().split())

print(countryOfNum -1)

• DFS 풀이

  import sys
  

def DFS(cur, answer):
visited[cur] = True

for next in graph[cur]:
    if visited[next] == False:
        answer = DFS(next, answer+1)

return answer

n = int(sys.stdin.readline().rstrip())

for i in range(n):
countryOfNum, flightOfNum = map(int, sys.stdin.readline().rstrip().split())

#graph 생성
graph = [[] for _ in range(countryOfNum+1)]
visited = [False]*(countryOfNum+1)

for j in range(flightOfNum):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)
else:
    answer = 0
    answer = DFS(1, 0)
    print(answer)

```