백준 11967: 불 켜기 - BFS

현재 방에서 스위치를 통해 불을 킨 후, 인접해 있는 방 중 불이 켜져있는 방에 들어가 스위치를 키게 끔 하였습니다.

이 것을 한 주기라고 보고, 한 주기에서 불을 킨 적이 있다면, 다시 1,1 부터 새롭게 들어갈 수 있는 방을 확인하게끔 하였습니다.

 

한 번 불을 켰다면 다시는 불을 키지 않아도 되게끔 'swithced_turned'라는 변수로 체크해 두었고, 이는 초기화 되지 않습니다.

새롭게 불이켜진 방이 있고, 그 방은 현재 이동 가능한 방과 인접해 있어 이동할 수 있는 경우가 될 수 있습니다.

따라서 매 주기마다 계속 이전에 와 봤던 방이라도 확인을 해주어야 하기 때문에 'visited'는 주기마다 초기화를 해주었습니다.

 

불을 켤 때 마다 count를 해주고, 주기가 끝날 때마다 'total_count'에 더해주고, 더 이상 불을 킬 수 없게 되면 종료됩니다.

from sys import stdin
from collections import deque
input = stdin.readline

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

def turn_on_light(n, switch_turned, room):
    queue = deque()
    visited = set()
    turned_light = False
    count = 0

    room[1][1] = True
    queue.append((1,1))
    visited.add((1,1))

    while queue:
        x, y = queue.popleft()
        if (x, y) not in switch_turned and (x, y) in switch_info:
            for nx, ny in switch_info[(x,y)]:
                if not room[ny][nx]:
                    room[ny][nx] = True
                    count += 1
            switch_turned.add((x, y))
            
        
        for ii in range(4):
            ny = y + dy[ii]
            nx = x + dx[ii]
            if not 0<ny<=n or not 0<nx<=n:
                continue
            if (nx, ny) in visited:
                continue
            if room[ny][nx]:
                queue.append((nx, ny))
                visited.add((nx, ny))
        
    return count


n, m = map(int, input().split())
switch_info = dict()

for _ in range(m):
    x, y, a, b = map(int, input().split())
    if (x,y) not in switch_info:
        switch_info[(x,y)] = []
    switch_info[(x,y)].append((a,b))

switch_turned = set()
total_count = 1
room = [[False for _ in range(0, n+1)] for _ in range(0, n+1)]

while True:
    count = turn_on_light(n, switch_turned, room)
    if not count:
        break

    total_count += count

print(total_count)