[백준 14466] 소가 길을 건너간 이유2 - python

문제

https://www.acmicpc.net/problem/14466

---

[사용한 알고리즘]

• BFS
• 시뮬레이션

[풀이]

본 문제는 BFS 를 사용하여 구현하였다. 비교적 다른 문제들에 어렵지 않은 문제니 쉽게 해결이 가능하다.

그러나 본인은 국어를 못하여 문제를 읽고 이해를 못해서 좀 늦게 풀린 감이 있다..

따라서 문제를 잘 읽어야한다.. 문제가 출력하길 요구하는것은 길을 건너지 않으면 만나지 못하는 소들의 쌍이다!!!

문제의 조건은 다음과 같다.

1. 농장에는 길이 존재한다. 인접한 목초지는 소들이 자유롭게 건널 수 있지만 일부는 길을 건너야 한다.
2. 건너야 하는 길이 처음에 주어진다.
3. 출력해야 하는 건 길을 건너지 않고서는 만날 수 없는 소들!

알고리즘 설명

1. 각 소의 위치를 cows 2차원배열에 담는다. ( cos[i][j] == 1 이라면 i행j열에 소가 존재한다는 의미이다. )
2. 각 소의 위치마다 BFS 를 수행한다.
3. BFS 내에서 소의 상하좌우 위치에 길이 존재할 시 에는 탐색을 생략한다. ( 소가 길을 건너지 않았을 때가 조건이므로 )
4. 소가 탐색한 위치는 0 으로 값을 바꾸어준다.
5. BFS 를 끝낸 뒤 cowmap 배열에서 1의 개수를 센뒤 count에 추가한다.
6. 소의 쌍을 출력해야 하므로 count // 2를 출력한다.

약 20분내로 풀었던 문제이기에 코드가 깔끔하지 않다. 그만큼 비교적 쉬운 문제이고 나의 코드를 참고하기보다는 문제를 이해하고 구현에 집중하자.

코드

import sys
from collections import deque
import copy
input = sys.stdin.readline

N, K, R = map(int,input().split())
farm = [ [[] for _ in range(N)] for _ in range(N) ]
visited = [ [False] * N for _ in range(N)]

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

cows = [ [0] * N for _ in range(N)]

count = 0

for _ in range(R):
    r1, c1, r2, c2 = map(int,input().split())
    farm[r1 - 1][c1 - 1].append([r2 -1, c2-1])
    farm[r2 - 1][c2 - 1].append([r1 - 1, c1 - 1])

for _ in range(K):
    r, c = map(int,input().split())
    cows[r-1][c-1] = 1

def bfs(position, visit, cowmap):
    q = deque()
    q.append(position)
    
    while q:
        r, c = q.popleft()
        if visit[r][c]:
            continue
        else:
            visit[r][c] = 1
            cowmap[r][c] = 0
            for i in range(4):
                nr = r + dy[i]
                nc = c + dx[i]
                position = (nr,nc)
                po_list = [nr,nc]
                roads = farm[r][c]
                
                if po_list in roads:
                    continue
                
                if 0 <= nr < N and 0 <= nc < N:
                    q.append(position)
    return cowmap

for i in range(N):
    for j in range(N):
        if cows[i][j]:
            cowmap = bfs((i,j), copy.deepcopy(visited),copy.deepcopy(cows))
        else : continue
        
        for k in range(N):
            for z in range(N):
                if cowmap[k][z]:
                    count += 1

print(count // 2)