백준 11967 불켜기

과정

• 불 켜는 곳 딕셔너리로 입력 받기
• bfs 로 가능한 곳 전부 순회하기
• 불켜진 곳과 방문한 곳 2차원 리스트를 따로 만들기
• 딕셔너리에서 찾아서 불을 켤 때, 불 켜지는 곳 사방 중 방문한 곳을 재검하기 위해 queue에 넣는다.
• 현재 위치에서 사방을 보며 불 켜지고 방문 안한 곳을 queue에 넣는다.

import sys
from collections import deque

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

dic = {}
for _ in range(M):
    x, y, a, b = map(int, input().split())
    if (x - 1, y - 1) in dic:
        dic[(x - 1, y - 1)].append((a - 1, b - 1))
    else:
        dic[(x - 1, y - 1)] = [(a - 1, b - 1)]

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

def bfs():
    lighted = [[False] * N for _ in range(N)]
    visited = [[False] * N for _ in range(N)]
    lighted[0][0] = True
    visited[0][0] = True
    queue = deque([(0, 0)])
    cnt = 1
    
    while queue:
        a = queue.popleft()
        x = a[0]
        y = a[1]
        if (x, y) in dic:
            for i in dic[(x, y)]:
                if not lighted[i[1]][i[0]]:
                    lighted[i[1]][i[0]] = True
                    cnt += 1
                    for j in range(4):
                        nx = i[1] + dx[j]
                        ny = i[0] + dy[j]
                        if 0 <= nx < N and 0 <= ny < N and visited[ny][nx]:
                            queue.append((nx, ny))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N and lighted[ny][nx] and not visited[ny][nx]:
                visited[ny][nx] = True
                queue.append((nx, ny))
    return cnt

print(bfs())

• 더 이상 불 켜는 곳이 없을 때까지 bfs를 처음부터 반복하게 했더니 7000ms 대가 나왔다.
• 불을 켤 때, 불을 켠 곳의 상하좌우 중 방문한 곳을 다시 확인하도록 queue에 넣도록 하니 시간이 많이 단축되었다.