백준 11967 불켜기

haruponea·2021년 3월 27일
0

BOJ

목록 보기
28/41

문제 링크https://www.acmicpc.net/problem/11967

풀이
일반적인 BFS보다는 까다로운 문제였습니다.

처음에는 불이 켜지면 bfs를 초기화 시켜 (1, 1)부터 다시 bfs를 도는 방법으로 했었는데 통과는 되지만 조금 더 시간을 줄일 수 있을 것같아 조금 더 생각해 보았습니다. 최적화 시키는 방법으로 bfs를 다 돌지말고 큐에 방문해야하는 칸만 추가해주는 방법을 선택했습니다.
큐에 추가되는 조건이 두가지가 있는데
1.현재 위치에서 불을 켜고 불이 켜진방 주위에 방문한 칸이 인접해 있으면 추가
2.현재 위치 주위에 방문하지 않은 칸이 있고 불이 켜져 있으면 큐에 추가
이 두가지를 구현하면 됩니다.

Python

from collections import deque, defaultdict
import sys
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
n, m = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
    x, y, a, b = map(int, sys.stdin.readline().split())
    graph[(x-1,y-1)].append((a-1,b-1))
def bfs():
    vis = [[False]*n for _ in range(n)]
    light = [[False]*n for _ in range(n)]
    vis[0][0] = True
    light[0][0] = True
    q = deque()
    q.append((0,0))
    cnt = 1
    while q:
        x, y = q.popleft()
        for conx, cony in graph[(x,y)]:
            if light[conx][cony] == False:
                light[conx][cony] = True
                cnt += 1
                for i in range(4):
                    nx, ny = conx + dx[i], cony + dy[i]
                    if 0<= nx < n and 0<= ny < n and vis[nx][ny] == True:
                        q.append((nx, ny))
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0<=nx<n and 0<=ny<n and vis[nx][ny] == False and light[nx][ny] == True:
                q.append((nx,ny))
                vis[nx][ny] = True
    print(cnt)
bfs()

0개의 댓글