[백준/파이썬] 11967번 불켜기

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

11967번: 불켜기

문제 해석

 

입력에서 n * n 크기의 방이 주어지고, m개의 입력이 주어진다.

m개의 입력에서는 x, y, a, b가 주어지고, (x, y)방에는 (a, b)방의 불을 켤 수 있는 스위치가 존재한다.

불을 켤 수 있는 방의 최대 개수를 출력하는 문제이다.

---

코드

 

from collections import deque

# input
input = __import__('sys').stdin.readline
n, m = map(int, input().split())
arr = [[0 for _ in range(n)] for _ in range(n)]
light = [[[] for _ in range(n)] for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

for _ in range(m):
    x, y, a, b = map(int, input().split())
    x -= 1
    y -= 1
    a -= 1
    b -= 1

    light[x][y].append((a, b))

def solve():
    visit = [[0 for _ in range(n)] for _ in range(n)]
    q = deque()
    q.append((0, 0))
    visit[0][0] = 1
    arr[0][0] = 1
    # 시작 지점 스위치 켜주기
    for a, b in light[0][0]:
        arr[a][b] = 1
    
    while q:
        i, j = q.popleft()
        for dir in range(4):
            x, y = i + dx[dir], j + dy[dir]
            if not(0 <= x < n and 0 <= y < n): continue
            if visit[x][y] == 0 and arr[x][y] == 1:
                visit[x][y] = 1
                q.append((x, y))
                for a, b in light[x][y]:
                    arr[a][b] = 1
                    
                    # 스위치 켜진 방으로 진입할 수 있다면 큐에 넣어주기
                    for dir in range(4):
                        aa, bb = a + dx[dir], b + dy[dir]
                        if not(0 <= aa < n and 0 <= bb < n): continue
                        if arr[aa][bb] == 1 and visit[aa][bb] == 1:
                            q.append((aa, bb))
                
    
    ans = 0
    for i in range(n):
        for j in range(n):
            if arr[i][j] == 1: ans += 1
    
    return ans      

print(solve())

---

문제 풀이

 

arr에는 방에 불이 켜져 있는지에 대한 정보를 담는다.

light에는 해당 방에 켤 수 있는 방에대한 좌표를 담는다.

 

초기에 (0, 0) 방에 불을 켜주고, 해당 방에 스위치를 켜 (0, 0)에 존재하는 스위치에 대한 방의 불을 켜준다.

BFS 탐색을 통해 불이 켜진 방에 진입하며 해당 방에 스위치를 켜준다.

 

이때 켜진 방에 visit 리스트 때문에 갈 수 없는 경우가 생길 수 있다.

따라서 방에 불을 켤 때 해당 방에서 상하좌우 방을 탐색하여 해당 방에 불이 켜져있고, 방문했다면 해당 좌표를 큐에 넣어주었다.

이 방법을 통해 매번 방문노드를 초기화 하여 탐색하지 않도록 하여 시간을 줄일 수 있다. -> 시간 초과도 나지 않는다!

 

탐색을 마치고 arr 완전탐색을 통해 불이 켜져 있는 방의 개수를 세어주면 된다.