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

문제

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

입력

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

출력

길을 건너지 않으면 만날 수 없는 소가 몇 쌍인지 출력한다.

 

문제풀이

import sys
from collections import deque

n,k,r=map(int, sys.stdin.readline().split(' '))

# dummy
graph=[[0]*(n+1) for _ in range(n+1)]
# 3차원 배열
ways=[[[] for _ in range(n+1)] for _ in range(n+1)]
for i in range(1,r+1):
    r,c,r_,c_=map(int, sys.stdin.readline().split(' '))
    ways[r][c].append((r_, c_))
    ways[r_][c_].append((r,c))

cow=[]
for _ in range(k):
    y,x=map(int, sys.stdin.readline().split(' '))
    cow.append((y,x))


def impossible_meet_cow(sy, sx, ey, ex):
    global ways
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    queue=deque()
    queue.append((sy,sx))
    visited=[[0]*(n+1) for _ in range(n+1)]
    visited[sy][sx]=1
    while queue:
        cury, curx=queue.popleft()
        if cury==ey and curx==ex:
            return False
        for di in directions:
            dy=cury+di[0]
            dx=curx+di[1]
            if 1<=dy<=n and 1<=dx<=n and visited[dy][dx]==0:
                # (dy,dx)가 ways[cury][curx]에 존재하는지 즉, 길을 건너야만 갈 수 있는 곳인지 확인
                if (dy,dx) not in ways[cury][curx]:
                    queue.append((dy,dx))
                    visited[dy][dx]=1
    else:
        return True

ans=0
for i in range(k):
    for j in range(i,k):
        # start cow
        sc_y, sc_x=cow[i]
        # end cow
        ec_y, ec_x=cow[j]
        if impossible_meet_cow(sc_y, sc_x, ec_y,ec_x):
            ans+=1

print(ans)

3차원 배열 ways[][][]에 각 위치에서 갈 수 없는 위치를 튜플 형태로 저장한다.

그리고 cow 배열에 소들의 위치를 저장한다.

 

2중 for문을 이용해서 소들의 위치 2개를 선택해주는데, 이때 중복을 피하기 위해서 첫번째 선택된 위치보다 인덱스가 큰 위치를 선택한다.

이렇게 선택된 출발 소의 위치와 도착 소의 위치를 impossible_meet_cow 함수를 통해서 길을 건너지 않고는 도착이 불가능한지 확인한다.

 

impossible_meet_cow 함수에서는 bfs 알고리즘을 사용하고, wheile...else...문을 이용한다. 

여기서, 탐색하는 큐에 위치를 넣어주는 조건은 격자판의 범위를 벗어나지 않으면서, 방문한 적 없고, 현재 위치에서 도달이 불가능한 위치가 아니면 넣어준다.

while문 안에서 도착 위치에 도달이 가능하면 False를 반환하고, 불가능하면 else문으로 들어가 True를 반환한다.