dfs로 구현을 하려고 했다. 맨 처음에는 섬세하게 접근을 하지 않아 각 노드에서부터 시작을 해서 양 방향으로 접근하려 했다. 만일 해당 문제에서 3과 4의 촌수를 알아야 한다면...
이러한 방식으로! 노드를 찾은 후 노드에서부터 전체 가계도를 훑고, 그 과정에서 cnt를 1씩 올려주려 했다. 만일 자식을 찾았을 경우에는 cnt를 answer list(밑 코드에서는 tmp)에 올려주고 tmp의 len이 1이라면(같은 가계도에 없는 경우라면...) -1을 출력하려 했으나...1이 노드가 아닐 경우를 고려해야 한다는 점과, 이를 보완하려면 노드를 찾아주는 코드를 따로 작성해야 한다는 점이 너무너무 귀찮고 까다로웠다. 그래서 그냥 양방향 그래프를 구현해준 후 내가 찾고자 하는 사람들에 대해서만 가계도를 돌려고 했다.
def dfs(root, cnt):
global ans
st = []
for i in range(len(tree[root])): #tree root에 있는 자식에 대해 전부 dfs를 할 거야
if tree[root][i] == peo1 or tree[root][i] == peo2:
ans += cnt
tmp.append(cnt)
return
else:
dfs(tree[root][i], cnt+1)
N = int(input())
peo1, peo2 = map(int, input().split())
M = int(input())
tree = [[] for _ in range(101)]
for _ in range(M):
par, chd = map(int, input().split())
tree[par].append(chd)
ans = 0
tmp = []
dfs(1,1)
if ans == 0 or len(tmp) == 1:
print(-1)
else:
print(ans)
ANS
노드를 기준으로 돌지 않고 3과 4의 촌수를 찾아야 한다면 해당 사람들을 기준으로 dfs를 하는 코드. 훨씬 간단하다!
def dfs(people, cnt):
cnt += 1
visited[people] = True
if people == p2:
ans.append(cnt)
for i in familytree[people]:
if not visited[i]:
dfs(i, cnt)
N = int(input())
p1, p2 = map(int, input().split())
M = int(input())
ans = []
familytree = [[] for _ in range(N+1)]
visited = [False]*(N+1)
for _ in range(M):
x,y = map(int, input().split())
familytree[x].append(y)
familytree[y].append(x)
dfs(p1,1)
if len(ans) == 0:
print(-1)
else:
print(ans[0]-2)
