gold 3 / 그래프 이론, 그래프 탐색, 너비 우선 탐색
문제 흐름
문제를 읽으면 이해가 좀 안될 수도 있다.
이 문제에서의 "길"은 벽과 같다고 이해해야한다.
길은 보통 건널 수 있는 요소로 등장하기 때문에 좀 헷갈릴만한 것 같다.
문제를 간단하게 설명하자면 농장에서 길로 나누어져서 못만나는 소의 쌍은 몇이나 되는가? 인데..,
- 길로 나누어진 농장 각 파트에 소가 몇마리씩 있는지 모든 농장에 대해서 체크한다.
- 구한 각각의 소 그룹을 둘씩 묶을 수 있는 모든 조합에 대해 소 숫자의 곱을 모두 더한다.
1번은 많이 해본 과정이다.
여기서 필요한건 💡길이 있을 경우 진행하지 않는 bfs를 수행하는 기능이겠다.
근데 이동하지 못하는 길이 두 목초지의 좌표로 주어지기 때문에 이를 어떻게 저장할지 고민이었다.
고민하다가 그냥 길을 놓을 위치까지 추가해서 농장을 3x3 ➡️ 5x5로 확대해서 진행하기로 했다.
그러면 파란색 부분(짝수 좌표)은 길을 놓기 위한 칸이 되고, 흰색 부분(홀수 좌표)은 소가 위치할 수 있는 목초지가 된다.
근데 이 방법에는 문제가 있다.
이 부분을 잡지 못해서 며칠 고민했는데 우연히 반례를 찾게 되어서 발견했다.
위와 같은 경우 정석대로 지도를 그리면 왼쪽과 같고 두 소가 만날 수 없어야 하지만, 내가 생각했던 방법처럼 오른쪽과 같이 변형하면 두 소는 길을 건너지 않고 만날 수 있게 된다.
앗차차..🥲
그래서 bfs를 진행할 때 방향으로 1칸 진행했을 때 길이 있으면 더이상 진행하지 않고, 없다면 1칸 더 진행하고 큐에 넣고 방문표시하는 식으로 진행했다.
💡소 그룹들의 모든 조합에 대한 소 수의 곱을 구하는 기능이 남았는데 이건 itertools의 combinations를 이용해 구했다.
코드
"""
소가 길을 건너간 이유 6
bfs
"""
import sys
from pprint import pprint
from collections import deque
from itertools import combinations
input = sys.stdin.readline
def bfs(sx: int, sy: int, Map:list, visit: list):
q = deque([(sx, sy)])
visit[sx][sy] = 1
n = len(visit)
count = 0
dir_x = [ 0,-1, 0, 1]
dir_y = [-1, 0, 1, 0]
while q:
x, y = q.popleft()
if Map[x][y] == 2: # cow
count += 1
for i in range(4):
nx = x + dir_x[i]
ny = y + dir_y[i]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if Map[nx][ny] == 1: # road
continue
nx += dir_x[i]
ny += dir_y[i]
if not visit[nx][ny]:
q.append((nx, ny))
visit[nx][ny] = 1
return count
def cows(Map: list, N: int):
visit = [[0 for i in range(N*2-1)] for j in range(N*2-1)]
cow_group = []
for i in range(0, N*2-1, 2):
for j in range(0, N*2-1, 2):
if visit[i][j] == 0:
cow_group.append( bfs(i, j, Map, visit) )
#print("visit:")
#pprint(visit)
#print(f"cow_group: {cow_group}")
res = 0
for group1, group2 in combinations(cow_group, 2):
res += group1 * group2
return res
if __name__ == "__main__":
N, K, R = map(int, input().split())
Map = [[0 for i in range(N*2-1)] for j in range(N*2-1)]
for r in range(R):
r1, c1, r2, c2 = map(lambda x: (x-1)*2, map(int, input().split()))
Map[(r1+r2)//2][(c1+c2)//2] = 1
for k in range(K):
r, c = map(lambda x: (x-1)*2, map(int, input().split()))
Map[r][c] = 2
print( cows(Map, N) )마무리
역시 본인이 쓴 코드를 리뷰하는 건 너무 어렵다.
내 코드는 완벽한데 어디가 틀린거지..! 라는 오만한 생각으로 리뷰해서 그런가. ㅎ..
이렇게 오래걸리다니 난 바보다.
