백준 2644 촌수계산

틀린 답 (dfs)

import sys

N = int(sys.stdin.readline().rstrip())
ox, oy = list(map(int, sys.stdin.readline().rstrip().split()))
M = int(sys.stdin.readline().rstrip())
graph = [[False] * (N + 1) for _ in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(M):
    x, y = list(map(int, sys.stdin.readline().rstrip().split()))
    graph[x][y] = True
    graph[y][x] = True

def dfs(node, cnt):
    visited[node] = True
    if node == oy:
        return cnt
    for i in range(1, M + 1):
        if graph[node][i] == True and not visited[i]:
            cnt = dfs(i, cnt + 1)
    return cnt

cnt = dfs(ox, 0)
if visited[oy]:
    print(cnt)
else:
    print(-1)

그림을 그려보고, 생각 없이 dfs로 풀었다.
명시된 테케는 통과하길래 그냥 제출했는데, 당연히 틀렸다.
뭐가 잘못된거지하고 bfs로 풀어봤다 ..

틀린 답 (bfs)

import sys
from collections import deque

N = int(sys.stdin.readline().rstrip())
ox, oy = list(map(int, sys.stdin.readline().rstrip().split()))
M = int(sys.stdin.readline().rstrip())
graph = [[False] * (N + 1) for _ in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(M):
    x, y = list(map(int, sys.stdin.readline().rstrip().split()))
    graph[x][y] = True
    graph[y][x] = True

q = deque([ox])
cnt = 0

while q:
    prev = q.popleft()
    flag = False
    if prev == oy:
        break
    for i in range(1, N + 1):
        if graph[prev][i] and not visited[i]:
            q.append(i)
            visited[i] = True
            flag = True
    if flag:
        cnt += 1

if visited[oy]:
    print(cnt)
else:
    print(-1)

그럼에도 또 틀렸다 도대체 와이!!!

정답 (dfs)

import sys

N = int(sys.stdin.readline().rstrip())
ox, oy = list(map(int, sys.stdin.readline().rstrip().split()))
M = int(sys.stdin.readline().rstrip())
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
res = [0] * (N + 1)

for _ in range(M):
    x, y = list(map(int, sys.stdin.readline().rstrip().split()))
    graph[x].append(y)
    graph[y].append(x)

def dfs(node, cnt):
    visited[node] = True
    res[node] = cnt
    for i in range(1, N + 1):
        if i in graph[node] and not visited[i]:
            dfs(i, cnt + 1)

dfs(ox, 0)

if visited[oy]:
    print(res[oy])
else:
    print(-1)

다시 dfs로 회귀했다.
여태 dfs풀때 그래프를 전부 False로 초기화 한 다음 True로 변환하는 방식으로 풀었었는데, 인터넷 풀이를 찾아보니 대부분 그래프를 이차원 배열 안에 연결된 요소를 넣는 방식으로 선언하는 것을 알게되었다.

그렇게 다시 선언하고, 기존에 한번 dfs하고 멈추던... 바보같은 방식을 고쳐서 다시 풀었더니 맞았다.

정답 (bfs)

그냥 넘어가기 아쉬워서 bfs로도 다시 풀어봤다.

import sys
from collections import deque

N = int(sys.stdin.readline().rstrip())
ox, oy = list(map(int, sys.stdin.readline().rstrip().split()))
M = int(sys.stdin.readline().rstrip())
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
res = [0] * (N + 1)
q = deque([ox])

for _ in range(M):
    x, y = list(map(int, sys.stdin.readline().rstrip().split()))
    graph[x].append(y)
    graph[y].append(x)

while q:
    prev = q.popleft()
    for i in range(1, N + 1):
        if i in graph[prev] and not visited[i]:
            q.append(i)
            res[i] = res[prev] + 1
            visited[i] = True

if visited[oy]:
    print(res[oy])
else:
    print(-1)

생각

문제의 관건이 누적되면서 합을 구하기보다, 새로운 배열을 하나 만들어서 거기에 각 노드별 촌수를 담아주는 것이라는 걸 알았다.
중요한건 dfs/bfs가 아니었다...!