728x90
반응형
https://www.acmicpc.net/problem/14466
문제
소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.
존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.
K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.
입력
첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.
출력
길을 건너지 않으면 만날 수 없는 소가 몇 쌍인지 출력한다.
풀이
Code
import sys
from collections import deque
input = sys.stdin.readline
# 1. bfs 함수 정의
def bfs(caw1, caw2) :
# 1-1. 방문 여부 리스트 생성
visited = [[False] * (n+1) for _ in range(n+1)]
# 1-2. 큐에 첫 번째 소의 위치 삽입
queue = deque()
queue.append((caw1[0], caw1[1]))
# 1-3. 첫 번째 소의 위치 방문 처리
visited[caw1[0]][caw1[1]] = True
# 1-4.
while queue :
# 큐에서 위치 인덱스 반환
x, y = queue.popleft()
for dir_x, dir_y in dirs :
nx, ny = x + dir_x, y + dir_y
# 예외 처리
if nx <= 0 or nx > n or ny <= 0 or ny > n : continue # 범위를 벗어난 경우
if (nx, ny) in roads[x][y] : continue # 길이 있는 경우
# 다음 위치를 방문하지 않은 경우
if not visited[nx][ny] :
# 방문 처리
visited[nx][ny] = True
# 큐에 다음 위치 삽입
queue.append((nx, ny))
# 1-5. 길을 건너도 되지 않는 경우 0, 길을 건너야 하는 경우 1 반환
return 0 if visited[caw2[0]][caw2[1]] else 1
n, k, r = map(int, input().split())
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
ans = 0
# 2. 길 정보 입력하기
roads = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(r) :
x1, y1, x2, y2 = map(int, input().split())
roads[x1][y1].append((x2, y2))
roads[x2][y2].append((x1, y1))
# 3. 소 위치 리스트 생성
caws = [list(map(int, input().split())) for _ in range(k)]
# 4.
for i in range(k) :
for j in range(i+1, k) :
# 4-1. bfs를 실행해 길을 건너는지 여부 확인
ans += bfs(caws[i], caws[j])
# 5. 결과 출력
print(ans)
728x90
반응형
'Coding Test > Baekjoon' 카테고리의 다른 글
[Python/BOJ] 12851. 숨바꼭질 2 (0) | 2023.07.25 |
---|---|
[Python/BOJ] 1987. 알파벳 (0) | 2023.07.25 |
[Python/BOJ] 1737. Pibonacci (0) | 2023.07.24 |
[Python/BOJ] 11279. 최대 힙 (0) | 2023.07.24 |
[Python/BOJ] 11724. 연결 요소의 개수 (0) | 2023.07.24 |