[ 백준 ] 11967 불켜기 (python)

 

 

 

 

 

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

11967번: 불켜기

 

 

💡 접근 방법

처음 문제를 보고 단순히 BFS를 사용해서 풀면 되겠다! 라고 생각했다.

그래서 주어진 (x, y) 방에서 (a, b)방 불 켤 수 있는 좌표들도 가볍게 list를 만들어 받아줬다.

이 과정에서 첫번째 오류 발생!

문제에서 주어진 방 하나에 여러 스위치가 있을 수 있다는 것이었다..😱

 

 

 

 

예제를 보고 얘기해보자면, (1, 1) 방에선 (1, 2)와 (1, 3) 방의 불을 킬 수 있는 스위치가 존재했다.

따라서 defaultdict를 활용해 (x, y)방에 존재하는 스위치 방을 모두 담아주었다.

 

그리고 기본적인 BFS 풀이 방법대로 queue를 생성하고, visited를 생성해 (1, 1)점을 시작으로 근접해있는 방이 불이 켜져 있다면 -> queue에 담는 방법으로 구현을 했다. 결과는 틀림😥

 

1️⃣ 왜냐면 (1, 1)을 방문하면 (1, 2)와 (1, 3) 방의 불을 켤 수 있다.

2️⃣ 하지만 (1, 1)방과 인접한 방은 (1, 2)이므로 (1, 2)를 queue에 담아준다.

3️⃣ 이어서 (1, 2)에서는 켤 수 있는 스위치 가 없음.

4️⃣ 그리고 (1, 2)에서 인접한 방을 방문해보면 (1, 3)만 불이 켜졌기 때문에 queue에 (1, 3)을 넣어준다.

5️⃣ (1, 3)에서 불을 켤 수 있는 방은 (1, 2)와 (2, 1) 방이다.

6️⃣ (1, 3)에서 인접한 방들 중 불이 켜져 있고, 방문하지 않은 방은 없다. 그러므로 bfs 함수가 종료된다.

 

문제가 원하는 풀이 과정은 이게 아니었으므로 당연히 틀린 결괏값이 반환됐던 것이다...😅

한참을 고민하다가 불이 켜져 있는 방을 확인하는 lights 리스트를 따로 만들어서 진행해 봤는데도 원하는 대로 풀리지 않았다. 그래서 다른 분의 풀이를 참고해 문제를 풀어냈다.

 

 

 

 

 

 

🔥 문제 풀이

 

우선 (1, 1)을 방문해서 불을 켤 수 있는 방의 불을 켜고, count 값을 1 더해준다 (lights[x][y] = 1, count += 1)

그리고 불을 켠 방에서 상, 하, 좌, 우를 확인해, 불 켜진 방과 인접하면서 이미 방문처리된 좌표를 찾아 queue에 담아준다.

 

* 다시 queue에 담아주는 이유 : 이미 방문한 곳이지만 불켜진 방과 인접하므로 다시 한번 검토를 통해 추가적으로 불을 켤 수 있는지 확인해준다 (매우 중요)

 

✨ 여기서 가장 헷갈렸는데 위에서 본 예시로 예를 들어 설명하면,

 

1️⃣ bfs 함수를 시작할 때, 시작점인 (1, 1)은 방문처리가 된 상태로 시작하게 된다. 따라서 (1, 1)의 스위치인 (1, 2)에서 인접한 곳 중 방문처리가 된 곳은 (1, 1)로 queue에 다시 한번 (1, 1)이 담기게 된다.

 

2️⃣ 이어서 (1, 1)에서 인접한 점 중 불이 켜진 곳을 찾아가 보자. (1, 1)과 인접한 방은  (1, 2)와 (2, 1)이 있다. 하지만 이땐 (2, 1) 방의 불이 켜지지 않은 상태이므로 (1, 2)만 queue에 담긴 채로 다음 과정으로 넘어간다.

 

3️⃣ 이후에 (1, 2)를 popleft를 통해 꺼내오고, (1, 2)와 인접한 (1, 3)을 queue에 담고 -> (1, 3)에서 (1, 2)와 (2, 1) 방의 스위치를 켜게 된다.

 

4️⃣ 그리고 1️⃣번에서 다시 한번 queue에 담겼던 (1, 1)을 pop 해서

인접한 방 && 아직 방문하지 않은 방 && 불이 켜진 방 => (2, 1) 방이 된다. 이제는 queue에 (2, 1)을 담아 (2, 1)에서 불을 켤 수 있는 다른 방들을 방문할 수 있게 된다. 

 

이와 같은 과정 때문에 불 켜진 방과 인접하면서, 이미 방문한 방은 queue에 다시 담아 재검토해주는 과정이 필요하다.

 

 

그리고 기존의 BFS 풀이 방법대로 pop으로 뽑힌 값의 인접한 곳을 확인해서 방문하지 않은 곳 && 불이 켜진 곳을 찾아 queue에 담아주면 된다.

 

 

 

from collections import defaultdict, deque
import sys
input = sys.stdin.readline
 
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
 
n, m = map(int, input().split())
info = defaultdict(list)
visited = [[False] * n for _ in range(n)]
lights = [[0] * n for _ in range(n)]
 
# defaultdict를 통해 불을 키고 끌 수 있는 방의 묶음을 담아준다
for _ in range(m):
    a, b, c, d = map(int, input().split())
    info[(a - 1, b - 1)].append((c - 1, d - 1))
 
 
def bfs():
    queue = deque()
    queue.append((0, 0))
 
    visited[0][0] = 1
    lights[0][0] = 1
    
    count = 1
 
    while queue:
        x, y = queue.popleft()
        
        # 현재 위치에서 불을 킬 수 있는 곳 찾아서 불 키기
        for a_, b_ in info[(x, y)]:
            if not lights[a_][b_]:
                lights[a_][b_] = 1
                count += 1
 
                # 불을 켤 수 있는 곳과 인접한 곳이 방문처리 된 곳이라면
                # 다시 한번 큐에 담아 준다
                # (다시 한번 방문해서 queue에 담아줄 내용이 변경됐는지 확인해야한다)
                for i in range(4):
                    na = a_ + dx[i]
                    nb = b_ + dy[i]
 
                    if na < 0 or na >= n or nb < 0 or nb >= n:
                        continue
 
                    if visited[na][nb]:
                        queue.append((na, nb))
 
        # 현재 위치에서 상하좌우로 이동해, 불켜져있다면 queue에 담아준다 
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
 
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
 
            if not visited[nx][ny] and lights[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True
 
    return count
 
print(bfs())