[파이썬] 백준 14466 : 소가 길을 건너간 이유 6 (골드 4)

[파이썬] 백준 14466 : 소가 길을 건너간 이유 6 (골드 4)

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

---

문제

---

풀이

0. 방향성 생각

• 각 소에서 BFS를 돌려서 도달하지 못하는 소의 수를 카운트한다.
• 다리가 있는 간선을 이용해야하면 이동하지 않는다.
• 쌍을 구하는 문제이므로 A->B, B->A 이런식으로 중복으로 카운팅이 된다.
• 이를 제거하기 위해서 소의 수를 모두 구한 후 2로 나누어주기.

1. 입력

from collections import deque
import sys

input = lambda : sys.stdin.readline().rstrip()

N,K,R = map(int,input().split())

arr = [[0]*(N+1) for _ in range(N+1)]

graph = set() # 간선 입력
for _ in range(R):
    y1,x1,y2,x2 = map(int,input().split())
    graph.add((x1,y1,x2,y2))
    graph.add((x2,y2,x1,y1))

cow = {} # 소 입력. 인덱스 필요
for i in range(K):
    y,x = map(int,input().split())
    arr[y][x] = 1
    cow[(x,y)] = i

inside = lambda x,y : 1<=x<=N and 1<=y<=N
dire = [(1,0),(-1,0),(0,1),(0,-1)]

• 특수한 간선인 다리는 set으로 처리한다. 양방향으로 처리를 해준다.
• 해시 대신 3차원 리스트를 만들어서 들어오는 방향에 따라서 boolean 형태로 나눠도 괜찮을 듯
• BFS에서 각 소를 구분하기 위해서 인덱스를 활용한다.

2. 함수 정의

def bfs(x,y,idx):
    
    visit = [[False]*(N+1) for _ in range(N+1)]
    visit[y][x] = True    
    C = [True]*K # 도달할 수 있는 소는 False
    C[idx] = False
    
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()
        
        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            
            if inside(nx,ny) and not visit[ny][nx] and (x,y,nx,ny) not in graph:
                visit[ny][nx] = True
                q.append((nx,ny))
                if arr[ny][nx] == 1:
                    C[cow[(nx,ny)]] = False
    return sum(C) # 어떤 소가 만나지 못하는 소의 수

• 도달할 수 있는 소를 나타내는 배열 C가 있다.
• 어떤 소에 도달할 수 있으면, 그 소를 False로 만든다
• sum(C)에는 어떤 소가 만나지 못하는 소의 수이다.

3. 출력

answer = 0
for idx,(x,y) in enumerate(cow):
    answer += bfs(x,y,idx)
print(answer//2) # 중복 제거

• 중복 제거하기위해 나누기 2

 

---

전체코드

from collections import deque
import sys

input = lambda : sys.stdin.readline().rstrip()

N,K,R = map(int,input().split())

arr = [[0]*(N+1) for _ in range(N+1)]

graph = set() # 간선 입력
for _ in range(R):
    y1,x1,y2,x2 = map(int,input().split())
    graph.add((x1,y1,x2,y2))
    graph.add((x2,y2,x1,y1))

cow = {} # 소 입력. 인덱스 필요
for i in range(K):
    y,x = map(int,input().split())
    arr[y][x] = 1
    cow[(x,y)] = i

inside = lambda x,y : 1<=x<=N and 1<=y<=N
dire = [(1,0),(-1,0),(0,1),(0,-1)]

def bfs(x,y,idx):
    
    visit = [[False]*(N+1) for _ in range(N+1)]
    visit[y][x] = True    
    C = [True]*K # 도달할 수 있는 소는 False
    C[idx] = False
    
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()
        
        for dx,dy in dire:
            nx,ny = x+dx,y+dy
            
            if inside(nx,ny) and not visit[ny][nx] and (x,y,nx,ny) not in graph:
                visit[ny][nx] = True
                q.append((nx,ny))
                if arr[ny][nx] == 1:
                    C[cow[(nx,ny)]] = False
    return sum(C) # 어떤 소가 만나지 못하는 소의 수

answer = 0
for idx,(x,y) in enumerate(cow):
    answer += bfs(x,y,idx)
print(answer//2) # 중복 제거

 

코멘트

.