5567번 - 결혼식

  • 0
  • 0
0
0

1. 결혼식

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😅 1차 시도 (실패 - 단방향만 고려함)
# 다익스트라
# 최단거리
# 최단 거리가 2 이하인 경우만 구함 (친구, 친구의 친구)

import heapq

n = int(input())
m = int(input())
graph = [[] for i in range(n+1)]

for i in range(m):
    a, b = list(map(int, input().split()))
    
    graph[a].append(b)  
    graph[b].append(a)
    
distance = [1e9] * (n+1)
distance[1] = 0

q = []
heapq.heappush(q, (1, 0))

while q:
    node, cost = heapq.heappop(q)
    if distance[node] < cost:
        continue
    for next_node in graph[node]:
        next_cost = cost + 1
        if next_cost < distance[next_node]:
            distance[next_node] = next_cost
            heapq.heappush(q, (next_node, next_cost))

count = 0
for i in range(2, len(distance)):
    if distance[i] <= 2:
        count += 1

print(count)


  • 반례

    10
    10
    4 10
    7 10
    3 7
    6 8
    1 7
    1 6
    1 5
    1 9
    2 4
    3 8
    
b. 😊 2차 시도 (성공)

# 다익스트라
# 최단거리
# 최단 거리가 2 이하인 경우만 구함 (친구, 친구의 친구)

import heapq

n = int(input())
m = int(input())
graph = [[] for i in range(n+1)]

for i in range(m):
    a, b = list(map(int, input().split()))
    # 주어진 친구를 graph로 입력받는다.
    graph[a].append(b)
    # 이 부분에서 A-B가 친구이면 B-A도 친구인 것을 인지했어야 한다.
    graph[b].append(a)
# 친구들의 최단 거리를 저장하는 dp
distance = [1e9] * (n+1)
# 상근이(나)의 최단 거리 초기화
distance[1] = 0

# 다익스트라 알고리즘에서는 보통 heap을 사용한다.
# 우선순위가 높은 것부터 삭제해야지 불필요한 연산이 진행되지 않기 때문이다.
# 하지만, graph 값으로 가지고 있는 것은 나와 친구인 node 번호만 가지고 있기 때문에 우선순위를 매길 것이 없다.
# 따라서, 단순 list로 구현해도 충분했을 것 같다.
q = []
heapq.heappush(q, (1, 0))

while q:
    # 우선순위가 가장 높은 node pop
    node, cost = heapq.heappop(q)
    # 저장된 현재 node의 최단 거리가 pop한 cost(최단거리)보다 작다면 continue
    if distance[node] < cost:
        continue
    # graph의 현재 node와 연결된 다른 node들을 탐색
    for next_node in graph[node]:
        # 최단 거리는 현재 node의 최단 거리 + 1로 증가한다.
        next_cost = cost + 1
        # 저장된 다음 node의 최단 거리가 next_cost보다 크다면 최단거리 갱신 및 heap에 추가
        if next_cost < distance[next_node]:
            distance[next_node] = next_cost
            heapq.heappush(q, (next_node, next_cost))

count = 0
# 최단 거리가 2 이하인 경우만 구함.
# 친구 = 1, 친구의 친구 = 2
for i in range(2, len(distance)):
    if distance[i] <= 2:
        count += 1

print(count)

a. 🙄 회고

내 풀이

  • 뭔가 다른 방법이 있어보였는데, 다익스트라가 보여서 다익스트라로 풀었다.

반성

  • 양방향을 생각하지 못했다.
    • 단방향만 고려하여 풀었을 때의 반례는 아래 해설에서 설명한다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.


10
10
4 10
7 10
3 7
6 8
1 7
1 6
1 5
1 9
2 4
3 8

단방향으로만 생각하면 이런식으로 그림이 그려진다.

이 경우 친구(빨간색)와 친구의 친구(초록색)를 표현하면 아래와 같다.

따라서 친구와 친구의 친구는 총 6명이다.

그런데 뭔가 이상하다.

3-7은 친구의 친구가 아닌 것일까?


이처럼 단방향만 고려한다면 3 -> 7은 친구의 친구로 고려되지 않는다.

따라서 7의 친구는 10만 존재하게 된다.

하지만 친구는 양방향으로 성립되기 때문에 7의 친구는 10과 3이 존재해야 한다.

그래서 2차 시도 코드처럼 수정하면 문제가 해결된다.

참고문헌

[1] baekjoon. 1065번: 한수 (acmicpc.net). Baekjoon. (accessed Dec 22, 2021)

[2] 문제 3. JOI 2009-2010 자격 질문 및 데이터 (ioi-jp.org). JOI. (accessed Dec 22, 2021)

0 minutes ago
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.