백준 11967 불켜기 파이썬

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

11967번: 불켜기

 

 

 

 

BFS 문제다. BFS 문제는 방문 처리를 어떻게 해야할지를 가장 먼저 고민하는 것이 국룰인 거 같다. 구해야하는 값은 "불이 켜져있는 방의 최대값"이다. 즉, 최소한 방문을 해야하는 것이 아니라, 가능한 모든 방을 다 방문해서 불을 켜야하는 것으로 이해를 할 수 있다.

​

이동 가능한 조건은 두 가지가 있다.

1. 불이 켜져있는 방에만 들어갈 수 있다 → 불이 켜져있는지 방인지 확인하는 배열의 생성 필요
2. 상하좌우만 가능하다 → 이동용 배열 생성 필요

​

따라서, Validation에서 위의 상황을 반드시 고려해야하는 것을 알 수 있다.

​

두번째로는 방문 체크의 최적화다.

예전에 방문했던 곳에서 다시 방문한 시점을 가정해보자. 이 때, 내가 예전에 방문했던 것과 동일한 상태라면 더 이상 방문할 필요가 없다. 그렇지만 내가 예전에 방문했을 때보다 하나라도 불을 켰으면 방문할 필요가 있다. 왜냐하면 내가 불을 하나 더 켜면서 이전에는 방문하지 못했던 곳에 방문할 수 있는 가능성이 있기 때문이다.

​

따라서 현재 불을 켠 상태 > V[next_r][next_c] 인 경우 방문할 수 있다는 결론이 난다.

​

​

세번째, 비트마스킹의 도입 여부다.

스위치는 2만개가 들어올 수 있고, 방의 갯수는 1만개다. 비트마스킹을 1만개를 해서 맵을 나누어 접근한다고 가정하며, 사실상 불가능하다. 2^10000 만큼의 방의 갯수가 필요하기 때문인데, 10000 * 2 ^ 10000일 경우... 딱 봐도 메모리 초과인 것을 이해할 수 있다.

​

​

결론은 아래와 같이 풀었다.

​

1. (1,1)에서 BFS를 돈다.
2. 특정 위치에 도착하면, 방문한 적이 있는지 확인한다.
   1. 방문한 적이 있으면, 현재 불이 켜져있는 수치와 방문 위치를 비교한다.
      1. 이 때, 켜져있는 숫자가 더 크면 한번더 큐에 넣는다.
   2.  해당 방에 방문한 적이 없으면, 방문의 스위치를 돌린다.
      1. 스위치를 돌릴 때, 켜고자 하는 방의 스위치가 켜져있는지 확인한다. 없으면, COUNT를 올려준다.
3. COUNT를 출력한다.

 

import sys
from collections import deque

def sol(my_map, r,c):
    global  ans
    temp = 0
    while my_map[r][c] :
        rrr, ccc = my_map[r][c].pop()
        if f[rrr][ccc] == 0:
            f[rrr][ccc] = 1
            ans += 1
            temp +=1
    return temp


def bfs(n):
    global ans, my_map

    # 초기화
    que = deque()
    v[1][1] = 1
    f[1][1] = 1
    ans +=1


    que.append((1,1))
    sol(my_map, 1,1)

    while que :
        r,c = que.popleft()

        for rr,cc, in tra_list:
            next_r, next_c = r + rr, c + cc

            if 0 < next_r < n+1 and 0 < next_c < n+1:
                # 불이 켜져있고 예전에 방문한 적이 있는 경우 (이 때만 방문이 가능하다)
                if f[next_r][next_c] == 1 and ans > v[next_r][next_c]:
                    #한번도 이 방에서 불켠 적이 없으면, 불을 켜준다.
                    sol(my_map, next_r, next_c)
                    v[next_r][next_c] = ans
                    que.append((next_r, next_c))





# 변수 입력 받기
n, m = map(int,sys.stdin.readline().split())
my_map = [[[] for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    sr,sc,dr,dc = map(int,sys.stdin.readline().split())
    my_map[sr][sc].append((dr,dc))
tra_list = [[1,0],[0,1],[-1,0],[0,-1]]


# 방문 배열을 만든다.
v = [[0 for _ in range(n+1)] for _ in range(n+1)]

# 불 켜진 곳인지 확인 배열
f = [[0 for _ in range(n+1)] for _ in range(n+1)]

ans = 0
bfs(n)
print(ans)