[백준/11967/파이썬] 불 켜기

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

11967번: 불켜기

Problem

• 농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.
• 베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

조건

• 베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다.
• 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 

SOL

그냥 BFS로 풀면 될것같은 문제였지만, 생각을 많이 해야하는 문제였다. 한 1시간정도 푼거 같은데, 다행히 풀렸다 !

여러방면으로 생각을 많이 해봤는데, Trobule shooting이 난 생각들을 적어보겠다.

 

Trouble shooting

 

CASE 1. 2차원 노드를 1차원 노드에 mapping을 해서 단순히 bfs를 돌리고, 불이 켜진 곳만 chk 해주면 되지 않을까?

 

생각보다 , 좋은 접근이였던것 같다. 애초에 2차원 맵을 bfs로 탐사한다는 의미 자체는 2차원 맵 하나하나 마다 node로 생각하고, 상,하,좌,우를 edge로 보는거니까. 예제도 통과를 해서  자신있게 제출을 했지만, 30%? 정도에서 틀렸다고 나왔다. 생각보다 간단한 반례에 깨져버렸다.

#불켜기
# N*N 의 map을 mapping하여, 인접리스트로 표현한 뒤, 탐색하자.
import sys
from collections import deque
input= sys.stdin.readline

N,M=map(int,input().split())
adj=[[] for _ in range(N*N)]
visited=[False for _ in range(N*N)]
def cvrt_zeroBase(y,x,a,b):
    return y-1,x-1,a-1,b-1

def mapping(y,x,a,b):
    return y*N+x%N,a*N+b%N

for i in range(M):
    y,x,a,b=map(int,input().split())
    y,x,a,b=cvrt_zeroBase(y,x,a,b)
    A,B=mapping(y,x,a,b)
    adj[A].append(B)
#print(adj)
def bfs(x):
    #adj에 있는 친구 받아서 , 
    visited[x]=True
    dq=deque()
    dq.append(x)
    while dq:
        x=dq.popleft()
        for nxt in adj[x]:
            if not visited[nxt]:
                visited[nxt] = True
                dq.append(nxt)
bfs(0)
cnt=0
#print(visited)
for v in visited:
    if v:
        cnt+=1
print(cnt)

 

반례)

1 1 2 2
2 2 3 3
3 3 4 4
2 2 1 2
3 3 3 2
4 4 4 3

위처럼, (1,1)에서 갈 수 있는 곳이 없을 때는,  (1,1)에서 켤 수 있는 불만 키고 끝을 내야하지만, 

위의 코드는 adj(인접리스트)에 따라 움직이므로, 리스트가 연결되어 있다고 하면, 방문할 수 있다고 착각을 한다. 

즉, 내가 실제로 갈 수 있는지 / 없는지의 정보가 반영되지 않았으므로, 이 부분을 추가적으로 구현을 해야한다.

 

CASE 2. 불을 키고 , 끄고 하는 정보를 (y,x) : [(a,b)...] (dictionary) 형식으로 저장한다음,bfs를 탐색해주면 되지 않을까? 

위의 풀이가 좌절되고, 그렇다면, 갈 수 있는지/없는지도 알아야하니까 결국 직접 시뮬레이션을 해주자 생각을 했고, 불 키는 정보는 따로 담아서 관리를 하는 형태로 구현을 했다.

이 부분 같은 경우는 dictionary로 key,value 쌍을 만들어 줄때, value에 있는 곳에서 아무런 불을 못키는 경우가 있는데, 그때마다, key error가 발생해서 골치가 아팠다. dictionary에 대해서 찾아보니, defaultdict이란게 있는데, keyerror가 났을때, error를 반환하지 않고, default value를 반환하는 아주 착한 친구가 있었다.

그걸 이용하니까 깔끔하게 해결된 문제!

import sys
from collections import deque,defaultdict

input= sys.stdin.readline

N,M=map(int,input().split())
visited=[[False for _ in range(N)] for _ in range(N)]
board=[[0 for _ in range(N)] for _ in range(N)]
turn_on=defaultdict(list)
dx=[0,1,0,-1]
dy=[1,0,-1,0]

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

#print(turn_on)
#print(turn_on.values())
#print(turn_on[(y,x)])
#왔다 갔다가 안되는데.

def bfs(y,x):
    ans=1
    dq=deque()
    dq.append((y,x))
    visited[y][x] = True
    board[y][x] =1
    while dq:
        y,x=dq.popleft()
        for a,b in turn_on[(y,x)]:
            if not board[a][b]:
                #불이 켜있지 않으면, 불을 키고, 방갯수를 하나 더 해준다.
                board[a][b]=1
                ans+=1
                for k in range(4):
                    na=a+dy[k]
                    nb=b+dx[k]
                    if not (0<=na<N and 0<=nb<N):
                        continue
                    #방문했던 적이 있던 곳은 , 돌아갈 수 있으므로, 다시 추가해준다.
                    if visited[na][nb]:
                        dq.append((na,nb))
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if not (0<=ny<N and 0<=nx<N):
                continue
            if board[ny][nx] and not visited[ny][nx]:
                dq.append((ny,nx))
                visited[ny][nx] = True
    return ans

print(bfs(0,0))