BOJ 2644

Input

일단 기본으로

1 2	import sys sys.setrecursionlimit(100000)

recursion limit 설정 값을 잘 파악하자

입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고,

둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다.

그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다.

넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

1 2	n = int(input()) x, y = map(int, input().split())

DFS

일단 촌수를 세는 규칙을 파악해야 하는데, 굉장히 간단하다.

트리 구조를 토대로, 위아래로만 count를 더해나가면 된다. 즉, 부모/ 형제 만을 기준으로 트리를 순회하면 됨.

연속적으로 adj 을 체크하므로 배열을 만들고

기본적으로 DFS라면, visited 를 생성하자.

1 2	adj = [[] for _ in range(n+1)] visited = [False] * (n+1)

for _ in range(int(input())):
  a, b = map(int, input().split())
  adj[a].append(b)
  adj[b].append(a)

관련이 없을 때는 -1을 출력해야 하므로, 이를 체크할 boolean 변수를 생성하자.
1
check = False

break point : 현재 체크하고 있는 값과 target 값이 같다면, 지금까지의 count 값을 출력하고 끝낸다.

if now == target:
  print(count)
  check = True
  return

이제 adj 배열에서 방문하지 않은 child에 대해 bfs를 진행한다.

def dfs(now, target, count):
  visited[now] = True
  global check

	  for child in adj[now]:
    if not visited[child]:
      dfs(child, target, count+1)

Another Solution

BFS로 queue 를 이용하는데, 모든 경우를 체크하는 경우이므로 이어서 값을 확인하기 좋다.

특히 깊이가 깊어질 때마다 count+1 을 수행하기에 큐가 적합하다.

while q:
        d = q.popleft()
        for i in s[d]:
            if visit[i] == 0:
                visit[i] = 1
                result[i] = result[d] + 1
                q.append(i)

이렇게 count를 배열로 설정하여 하나씩 더해가고, 정답을 출력하기 위해

1	print(result[b] if result[b] != 0 else -1)

해당 index로 바로 접근해서 출력하고 아닌 경우도 쉽게 예외 처리할 수 있다.

Output

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다.

어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

여기서 위에서 생성한 check 변수를 활용하면 된다. global 로 선언하였기 때문에, 비동기 처리되어 dfs가 모두 끝난 뒤 if문을 체크하게 된다.

dfs(x, y, 0)

if not check:
  print(-1)