[백준/11967] 불켜기 (Python)

Problem : https://www.acmicpc.net/problem/11967

11967번: 불켜기

 

Difficulty : Gold 2

 

Status : Solved

 

Time : 00:10:34

 

---

 

문제 설명

 

 

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

 

 

입력 및 출력

 

입력

 

첫 번째 줄에는 N(2 ≤ N ≤ 100)과, M(1 ≤ M ≤ 20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

 

출력

 

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

 

입력 예시

 

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

 

출력 예시

 

5

 

 

---

 

풀이

 

그래프 탐색을 진행하되, 현재 그래프에서 방문할 수 있는지 여부(즉 불이 켜졌는지 여부)를 저장해야 한다.

 

• 현재 좌표에서, 우선 켤 수 있는 스위치는 모조리 켠다.
  • 대상 좌표의 불이 켜졌는지에 대한 여부를 업데이트한다. 
  • 만약 방문하였되 들어갈 수 없었던 좌표라면, 그 좌표를 방문 큐에 삽입해주자.
• 현재 좌표에서 상하좌우를 탐색한다.
  • 유효한 좌표이며( -1 < x, y < N ) 방문하지 않았다면 우선 방문 여부를 업데이트한다.
  • 만일 불이 켜진 좌표라면 그 좌표를 방문 큐에 삽입하고, 그렇지 않으면 넘어간다.

 

모든 과정을 마치면, 불이 켜져있는 방 리스트를 구할 수 있으므로 그 합 역시 도출 가능하다!

 

 

풀이 코드

from collections import defaultdict, deque
import sys
input = sys.stdin.readline
cvt = lambda x : int(x)-1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

N, M = map(int, input().split())

switch_dict = defaultdict(list)
for _ in range(M) :
  x, y, a, b = map(cvt, input().split())
  switch_dict[(x, y)].append((a, b))

enable = [[0]*N for _ in range(N)]
visited = [[False]*N for _ in range(N)]
enable[0][0] = 1
visited[0][0] = True
q = deque([(0, 0)])

while q :
  x, y = q.popleft()

  for _x, _y in switch_dict[(x, y)] :
    if not enable[_y][_x] :
      enable[_y][_x] = 1
      if visited[_y][_x] :
        q.append((_x, _y))

  for k in range(4) :
    ax, ay = x + dx[k], y + dy[k]
    if -1 < ax < N and -1 < ay < N and not visited[ay][ax] :
      visited[ay][ax] = True
      if enable[ay][ax] :
        q.append((ax, ay))

print(sum(map(sum, enable)))

풀이 완료!