[Python] BOJ 11967 - 불켜기

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

11967번: 불켜기

# BFS문제이다. 처음에 일반 bfs함수처럼 진행을 해봤다.

   상하좌우로 이동하며 이동한 칸에서 불을 킬 수 있으면 불을 키고 다시 상하좌우로 이동...

   문제예제에서 (1, 1)에서 (1, 2), (1, 3)을 간 뒤 (2, 1)에 불을 키는것 까지는 할 수 있지만,

   (1, 3)에서 (2, 1)은 갈 수가 없다. ((1, 2), (1, 1)이 이미 visited되었기 때문에)

 

# 따라서, 방문가능한 칸과 불을 킬 수 있는 칸을 다 구해준 뒤, 한번에 처리를 했다

 

import sys
from collections import deque, defaultdict
input = sys.stdin.readline
N, M = map(int,input().split())
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
visited = [[False] * (N+1) for _ in range(N+1)]     # 방문한 칸
candidate = [[False] * (N+1) for _ in range(N+1)]   # 방문가능한 칸
light = [[False] * (N+1) for _ in range(N+1)]       # 불 켜진 칸
dic = defaultdict(list)
q = deque()

def bfs():
    # (1, 1)에 불켜고 방문하면서 시작
    answer = 1
    q.append((1, 1))
    visited[1][1] = True
    light[1][1] = True
    
    while q:
        x, y = q.popleft()
        # (x, y)칸에서 불 킬수 있는 칸 다 켜주고 answer += 1
        for d in dic[(x, y)]:
            if not light[d[0]][d[1]]:
                light[d[0]][d[1]] = True
                answer += 1
        
        # (x, y)칸에서 상하좌우 중 이동 가능한 칸 candidate[nx][ny] = True
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 1 <= nx <= N and 1 <= ny <= N:
                candidate[nx][ny] = True

        # (1, 1)부터 (N+1, N+1)까지 반복문 돌며, 방문하지 않고 불켜져 있으며 
        # 방문 가능한 칸을 만나면 그 칸 방문처리하고 q에 append
        for i in range(1, N+1):
            for j in range(1, N+1):
                if not visited[i][j] and light[i][j] and candidate[i][j]:
                    visited[i][j] = True
                    q.append((i, j))

    return answer

for _ in range(M):
    x, y, a, b = map(int,input().split())
    dic[(x, y)].append((a, b))

print(bfs())

(solved.ac 티어: 골드 3)