[Python] 11967번 불켜기

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

11967번: 불켜기

---

 

23/12/30

 

 

BFS 응용 문제로, 생각했던 풀이 방법보다 더 쉬운 방법이 있어서 글을 써본다.

---

 

초반 문제 접근 방식:

 

 

초반에 접근했던 문제 방식은 BFS를 한 번만 돌도록 하는 방식이었다.

 

문제를 보면, 특정 방에서 다른 방들의 스위치를 킬 수 있다고 했다.

 

그리고 스위치가 켜져 있는 방만 출입할 수 있다고 했고, 방에서 방으로 움직일 때에는 상하좌우 주변 네 방향으로만 움직일 수 있다고 했다.

 

이를 보고, 이전에 해결했던 문제와 매우 유사한 상황이라고 생각하여, 이 방식으로 문제를 접근했다.

 

그 문제에 대한 해설은 아래와 같다.

 

2022.10.29 - [알고리즘/백준 문제 풀이] - [Python] 20130번 Metroidvania Extreme

[Python] 20130번 Metroidvania Extreme

 

이 문제 또한 열쇠를 얻어 특정 구역을 여는데, 그전까지는 방문했던 영역을 뒤로 미루며 다시 넣는 아이디어를 취한다.

 

이와 같이 이 문제 또한 그렇게 접근했다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11967번 불켜기
# BFS
import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().rstrip().split())
mapping = dict()
for _ in range(M):
    x, y, a, b = map(int, input().rstrip().split())
    if (x, y) in mapping:
        mapping[(x, y)].append((a, b))
    else:
        mapping[(x, y)] = [(a, b)]
switch_on = set()
switch_on.add((1, 1))

dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
now_pos = (1, 1)
queue = deque()
queue.append(now_pos)
visited = [[0 for _ in range(N)] for _ in range(N)]
visited[0][0] = 1
while queue:
    now_pos = queue.popleft()
    if visited[now_pos[0]-1][now_pos[1]-1] > 5000:
        break
    if now_pos not in switch_on:
        queue.append(now_pos)
        visited[now_pos[0]-1][now_pos[1]-1] += 1
        continue
    if now_pos in mapping:
        for pos in mapping[now_pos]:
            switch_on.add(pos)
    for i in range(4):
        nr, nc = now_pos[0]+dr[i], now_pos[1]+dc[i]
        if 1 <= nr <= N and 1 <= nc <= N:
            moved_pos = (nr, nc)
            if visited[nr-1][nc-1] == 0:
                visited[nr-1][nc-1] = 1
                queue.append(moved_pos)
print(len(switch_on))

---

 

이후 접근 방식:

 

 

좀 더 쉽고 직관적인 접근 방식은 그냥 BFS를 한 번만 하는 것이 아닌 불을 키는 행위를 할 때마다 BFS를 하는 것이었다.

 

그렇게 해도 시간 초과 없이 잘 넘어갈 수 있었으며, 오히려 시간이 매우 단축되는 효과를 얻을 수 있었다.

 

BFS를 여러 번 하는 것에 대한 종료 조건은 더 이상 불을 킬 수 없을 때로 설정하면 충분하다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11967번 불켜기
# BFS
import sys
input = sys.stdin.readline
from collections import deque

def BFS(N, mapping, switch_on):
    dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
    now_pos = (1, 1)
    queue = deque()
    queue.append(now_pos)
    visited = set()
    visited.add(now_pos)
    while queue:
        now_pos = queue.popleft()
        for i in range(4):
            nr, nc = now_pos[0]+dr[i], now_pos[1]+dc[i]
            moved_pos = (nr, nc)
            if ((1 <= nr <= N) and (1 <= nc <= N)
            and (moved_pos not in visited) and (moved_pos in switch_on)):
                queue.append(moved_pos)
                visited.add(moved_pos)
                if moved_pos in mapping:
                    for pos in mapping[moved_pos]:
                        switch_on.add(pos)
    return switch_on

def main():
    N, M = map(int, input().rstrip().split())
    mapping = dict()
    for _ in range(M):
        x, y, a, b = map(int, input().rstrip().split())
        if (x, y) in mapping:
            mapping[(x, y)].append((a, b))
        else:
            mapping[(x, y)] = [(a, b)]

    switch_on = set()
    switch_on.add((1, 1))
    if (1, 1) in mapping:
        for pos in mapping[(1, 1)]:
            switch_on.add(pos)

    ans = len(switch_on)
    while True:
        switch_on = BFS(N, mapping, switch_on)
        if len(switch_on) == ans:
            break
        ans = len(switch_on)
    print(len(switch_on))

main()