[2644. 촌수계산]

세줄 요약
1. 이 개같은 문제 때문에 내 주말이 날라갔다. 아뤼십더 킹~!
2. 도저히 안되겠어서 정신건강상 치팅을 했다. 풀고도 찝.찝. ;;
3. 고수님들아 응용력은 언제 길러지는거임?

링크텍스트

이 문제는 촌수 계산, 약간 Tree에서 최단경로 따위? 랑 비슷한 논리를 쓰는 것 같기도 함. 최단경로도 풀어봐야징
내가 이 문제에서 제일 고민했던 건 :

Tree 깊이 판단을 어떻게 코드로 예쁘게 할까?

알고보니 새로운 list를 하나 만들어서 일괄적으로 입력해놓는 것이 가장 맘 편한 과정이었다.

n = int(input()) # 사람 수
a,b = map(int,input().split()) # 촌수 계산의 대상 2명
m = int(input()) # 부모 자식들 간의 관계 개수
graph = [[] for _ in range(n+1)] # 0번째 항 fake, 1~n
for _ in range(m):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x) # 연결 조건 생성
check = [0 for _ in range(n+1)] # 각 node 거쳐갔는지 확인하는 용도

위 부분은 입력 매만지기 프로세스. Skip.

def chon(p):
    for k in graph[p]:
        if check[k] == 0: # 하위 노드가 체크 안된 노드라면,
            check[k] = check[p] + 1
            chon(k)

휘바 휘바 위 코드가 내가 개x1000 애먹은 부분인데, 이렇게 간단하다.
node 하나만 딱 기준 잡아놓고, 나머지 node로 가는 경로의 숫자를 일괄적으로 싹 뽑자는 것이다.
** minor한 오류가 있는데, 자기자신 node번째 항은 0이 되지 않는다는 것

❌ 내가 바보짓 한 코드 :

def chon(p,q):
    global choncount
    global jamjung
    if check[p] == 0: # 처음 체크하는 사람이라면?
        check[p] = 1  # check 표시하고
        choncount += 1
        if q in graph[p]:
            jamjung = choncount
        for k in graph[p]:
            if check[k] == 0 and k!=0:
                chon(k,q)

이건 내가 생각을 뭘 개복잡하게 했는지, dfs 재귀함수 안에 2개 변수 넣어서 한번에 뽑아보려는 오만한 생각을 했다.
어이 뉴비. 욕심부리지 말고 원시적으로 하는 것도 나쁘지 않아.

chon(a)
if check[b] != 0:
    print(check[b])
else:
    print(-1)