14466. 소가 길을 건너간 이유 6 (Python)

 

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

 

풀이

 입력 받은 길은 문자열 형태로 만들어서 딕셔너리를 통해 기록했다. 만약 입력으로 2 2 2 3이 주어졌다면 "2 2 2 3"과 "2 3 2 2"의 형태로 딕셔너리의 키 값을 만들어서 길이 있음을 표시했다.

 

 모든 소에 대하여 bfs 탐색을 진행한다. 이때, (x, y)에서 (nx, ny)로 이동할 때 길이 존재한다면 그쪽으로는 이동하지 않도록 한다. 즉, 길이 없는 곳으로만 이동하여 탐색하고 이때 만났던 소들을 체크한다. bfs 탐색이 끝났을 때 만나지 못한 소가 있다면 그 소는 현재의 소와 길을 건너지 않고는 만나지 못하는 소임을 알 수 있다.

 

코드

import sys
from collections import defaultdict
input = sys.stdin.readline


# 범위 체크 함수
def isRange(x, y):
    return 1 <= x <= N and 1 <= y <= N


# 소의 위치에서 bfs로 체크 
# 현재 위치에서 상하좌우로 이동할 때 만약 길이 있다면 그 쪽으로는 가지 않는다.
# 길이 있는 경로는 가지 않았을 때 n번 소와 m번 소가 만난적이 없다면
# 이는 n번 소와 m번 소는 길을 건너지 않으면 만날 수 없는 소에 해당한다는 것을 알 수 있다.
def bfs(x, y):
    q = [(x, y)]
    visited = [[False for _ in range(N+1)] for _ in range(N+1)]
    visited[x][y] = True
    meetCows = [False for _ in range(K+1)] # 소가 길을 건너지 않고 만날 수 있는지를 체크하기 위한 배열 
    meetCows[0], meetCows[board[x][y]] = True, True # 사용하지 않는 0번 소와 자기 자신은 True로 설정

    while q:
        x, y = q.pop(0)

        for (dx, dy) in dir:
            nx = x + dx
            ny = y + dy

            if not isRange(nx, ny) or visited[nx][ny]:
                continue
            
            key1 = str(x) + " " + str(y) + " " + str(nx) + " " + str(ny)
            key2 = str(nx) + " " + str(ny) + " " + str(x) + " " + str(y)

            # (x, y)에서 (nx, ny)로 가는 길에 길이 있다면 체크하지 않음 
            if roads[key1] != 0 or roads[key2] != 0:
                continue

            visited[nx][ny] = True
            q.append((nx, ny))

            if board[nx][ny] != 0:
                meetCows[board[nx][ny]] = True # 길을 건너지 않고 만날 수 있는 소에 해당하므로 True로 변경

    return meetCows.count(False) # 길을 안건넜을 때 만나지 못한 소의 개수 


if __name__ == '__main__':
    # N: 농장의 크기, K: K마리의 소, R: 길의 수
    N, K, R = map(int, input().split())
    board = [[0 for _ in range(N+1)] for _ in range(N+1)]
    cows = []
    dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    roads = defaultdict(int)

    # 길 입력
    # 딕셔너리를 활용하여 (r1, c1)에서 (r2, c2)로 갈 때 길이 있는지를 체크한다
    for _ in range(R):
        r1, c1, r2, c2 = map(int, input().split())
        key1 = str(r1) + " " + str(c1) + " " + str(r2) + " " + str(c2)
        key2 = str(r2) + " " + str(c2) + " " + str(r1) + " " + str(c1)
        roads[key1] += 1
        roads[key2] += 1

    # 소 위치 입력
    # 소는 1부터 K까지의 값으로 설정 
    for i in range(1, K+1):
        r, c = map(int, input().split())
        board[r][c] = i
        cows.append((r, c))

    res = 0
    for i in range(K):
        res += bfs(cows[i][0], cows[i][1])

    # 중복 체크되는 쌍이 있으므로 2로 나누어준다.
    print(res // 2)