[Python] 백준 14466 소가 길을 건너간 이유 6

1. 문제 링크

14466번: 소가 길을 건너간 이유 6

14466번: 소가 길을 건너간 이유 6

---

2. 문제 요약

• 길을 이용해야 하는 소들 쌍을 구하는 문제

• 예제 문제를 그려보면 아래와 같다. 소의 위치와 길의 위치가 주어지고, 두 소가 쌍을 지어 서로 길 없이 만날 수 있는지 확인을 해야 한다.

---

3. 아이디어 정리

1. 소를 한 마리씩 돌려주면서(소 1) 정해진 길 없이 길을 건널 때 방문 여부를 모두 체크 ⇒ bfs
2. 1에서 구한 소 1의 방문 여부 결과에서 소 2의 위치에 방문을 못한 경우 count + 1

---

4. 문제 풀이

4-1. 내 풀이

"""
  정해진 길을 이용해야하는 소들 쌍
"""
import sys
from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(r1, c1):
    dq = deque()
    dq.append((r1, c1))
    cow_visit[r1][c1] = True
    while dq:
        x, y = dq.popleft()
        for d in range(4):
            nx = dx[d] + x
            ny = dy[d] + y
            # 범위 체크
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if cow_visit[nx][ny]:  # 방문 체크
                continue
            if (nx, ny) in road[x][y]:  # 다리인 경우 pass
                continue
            dq.append((nx, ny))
            cow_visit[nx][ny] = True

n, k, r = map(int, sys.stdin.readline().split())  # n*n, k: 마리, r: 정해진 길 

road = [[[] for _ in range(n)] for _ in range(n)]
cow_visit = [[False] * n for _ in range(n)]
count = 0
# 길 위치 담기
for _ in range(r):
    r1, c1, r2, c2 = map(int, sys.stdin.readline().split())
    road[r1 - 1][c1 - 1].append((r2 - 1, c2 - 1))
    road[r2 - 1][c2 - 1].append((r1 - 1, c1 - 1))

# 소의 위치 담기
cow_list = list()
for _ in range(k):
    a, b = map(int, sys.stdin.readline().split())
    cow_list.append((a - 1, b - 1))

# 1. 소를 한마리씩 돌려가면서 방문 여부 탐색
for i, cow in enumerate(cow_list):
    cow_visit = [[False] * n for _ in range(n)]
    # 2. 현재 소가 정해진 길 없이 가는 경로를 탐색
    bfs(cow[0], cow[1])
    for r2, c2 in cow_list[i + 1:]:
        # 3. 방문을 완료하지 못한 경우 결과 + 1
        if not cow_visit[r2][c2]:
            count += 1
print(count)

 

---

5. 결론

• 문제 자체를 이해하기 어려웠던 문제 ⇒ 문제를 더 상세하게 설명해주면 좋을 듯하다.😕
• 기본적인 bfs에 다리가 존재하는 경우 방문을 안 하도록 하면 되는 문제