백준 2644(촌수 계산) -BFS

무려 4번째에 맞게 된 문제라 기록하고 싶어서 게시 ㅎㅎ

처음엔 단순하게 부모 자식 관계를 노드-간선으로 보고 bfs로 풀어 cnt 로 값을 반환해주려고 했으나,

cnt로 값을 올리면 같은 거리의 (자식 관계) 값이 달라지게 된다. 따라서 테스트케이스에서는 정답이 나왔으나 백준에서 탈락을 한 것이다....

무엇이 문제일까?

아무리 생각해봐도 답이 안나온다.. 더욱이 테케는 통과되기 때문에...

그래서 도움을 요청했다. 이 문제는 다른 개념으로 봐야한다. distance라는 배열이 나온다!

시작하는 노드의 distance는 무조건 0.

부모 노드에 포함되는 자식노드의 distance는 부모 노드의 distance값에서 1을 더한 값으로 모두 동일하게 들어간다.

cnt로 계산하면 같은 자식이지만, 2, 3 이렇게 거리가 다르게 나와서 오류를 범하게 되는것!

 

-처음 오류난 코드

# 주어진 두 사람의 촌수를 계산하라.
# N: 전체 사람 수(노드 개수)
# X, Y: 두 사람의 번호
# M: 관계 개수(간선 개수)
# m, s: 부모 자식 관계
# 두 사람 관계가 없을 때는 -1반환

from collections import deque

def BFS(a,b):
    global cnt
    queue = deque()
    queue.append(a)
    visited[a] = True
    cnt += 1
    while queue:
        now = queue.popleft()
        for i in graph[now]:
            if i == b:
                return cnt
            if not visited[i]:
                visited[i] = True
                queue.append(i)
        cnt += 1
    return -1

cnt = 0
N = int(input())  # 노드 개수
X, Y = map(int, input().split())  # 두 번호
M = int(input())  # 간선 개수
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(M):
    m, s = map(int, input().split())
    graph[m].append(s)
    graph[s].append(m)

print(BFS(X, Y))

-수정한 코드

# 주어진 두 사람의 촌수를 계산하라.
# N: 전체 사람 수(노드 개수)
# X, Y: 두 사람의 번호
# M: 관계 개수(간선 개수)
# m, s: 부모 자식 관계
# 두 사람 관계가 없을 때는 -1반환

from collections import deque

def BFS(a,b):
    queue = deque()
    queue.append(a)
    visited[a] = True
    distance[a] = 0
    while queue:
        now = queue.popleft()
        for i in graph[now]:
            if not visited[i]:
                if i == b:
                    distance[i] = distance[now] + 1
                    queue.append(i)
                    return distance[i]
                visited[i] = True
                distance[i] = distance[now] + 1
                queue.append(i)
    if b not in queue:
        return -1


N = int(input())  # 노드 개수
X, Y = map(int, input().split())  # 두 번호
M = int(input())  # 간선 개수
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
distance = [0] * (N + 1)

for _ in range(M):
    m, s = map(int, input().split())
    graph[m].append(s)
    graph[s].append(m)

print(BFS(X, Y))

-- 뭔가 복잡해 보여서 좀 더 단순하게 만들어 보는 노력을 해봐야겠다. 하지만 아직은 그것까지는 힘든 수준이다. ㅜㅜ