99클럽 코테 스터디 8일차 TIL: 그래프 탐색 및 DP

오늘의 문제 | 2644. 촌수계산

문제를 보자마자 그래프 문제라는건 바로 알 수 있다. 그래서 입력 부분부터 코드짜고 생각해보니, 로직이 떠오르게 되었다.

아이디어: DP로 해결할 수 있지 않을까

물론 이걸 DP라 해야할지 전처리 과정이라 해야할지 모르겠지만, 우선 n이 크지 않기 때문에 이론상 시작하기 전 루트를 기준으로 촌수를 구하고 해당 촌수들만 빼면 어떨까 했었다.

사실 이게 가능한게 부모가 최대 한 명이라는 점에서 크게 문제가 없지 않을까 생각했었다. 하지만 촌수를 계산 하는건 꽤나 복잡한 과정이기이 전처리로 문제를 해결 할 수 없었다.

아이디어: 문제를 복잡하게 생각하지 말자

생각보다 문제가 단순하지 않을까 생각했다. 어차피 결혼 관계가 없기 때문에 부모자식 간 1촌, 즉 거리만 계산하면 되는 것이다. 근데 탐색의 출발지점이 주어졌으므로 출발지점을 기준으로 몇 칸 떨어졌나가 결국 촌수의 기준인 것이다.

이건 하나의 값과의 거리를 찾는 것이긴 하지만, 연결되지 않았음을 찾아내기 어렵기에 모두 탐색해보고 지나가지 않은 공간을 -1로 두면 찾아내기 쉽지 않을까 싶다.

그리고 깊이를 알아야 하기에 bfs를 통해 풀어야 하지 않겠냐는 생각이 들었다. 처음에는 상관없을줄 알았는데 효율적인 검색을 위해서는 필요해 보인다. bfs를 구현하는건 그냥 리스트로 해도 상관은 없지만 큐로 하려고 한다.

from collections import deque

n=int(input())
p1,p2=map(int,input().split())
m=int(input())
graph=[[] for i in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

visit=[-1 for i in range(n+1)]
idx=0

def bfs(graph, start):
    global idx, visit
    stack=deque()
    stack.append(start)
    visit[start]=idx
    idx+=1

    while stack:
        node=stack.popleft()
        idx=visit[node]
        node_connected=graph[node]
        
        for i in node_connected:
            if visit[i]==-1:
                visit[i]=idx+1
                stack.append(i)
            else: continue

bfs(graph, p1)
print(visit[p2])

문제를 한번에 해결하는걸 성공했다. 그래프 문제여서 오래걸리려나 걱정했는데, 어떻게 visit을 이용해야 할지에 대한 생각만 좀 하다보니 금방해결할 수 있었다.

오늘의 회고

그래프 중 확실히 실버는 아직 풀만하다는 생각이 든다. 기본적인 DFS, BFS 정도는 코드를 참고할 필요없이도 짤 수 있다는 생각도 들고, 문제를 보고 둘 중에 뭘 써야 할지를 알아냈다는 사실이 놀랍긴하다. 점점 짬이 차는 것일까 싶기도 하다. 그나저나 문제 제출 사진을 실수로 잘못낸거 같은데 문제가 생기진 않겠지..