[백준 11967번] 불켜기(파이썬)

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

11967번: 불켜기

이 문제는 까다로운 지점이 많습니다.

우선, 그림으로 이 문제에서 봐야할 걸 보겠습니다.

바로 방문한 곳을 다시 갈 수 있는 점입니다.

조건에 불켜진 곳만 방문할 수 있다고 적혀있습니다.

그래서 처음에는 가지 못하는 곳이

다른 곳을 방문하면서 스위치를 키면

방문이 가능해집니다.

그런데 bfs를 구현하다보면

'한번 방문한 곳은 다시 방문하지 않는다'

라고 하잖아요.

왜냐하면 탐색이 중복되니깐.

 

저는 깔끔하게 이렇게 생각했습니다.

'스위치가 있는 구역에서 스위치를 키면

방문했던 곳을 초기화하면 되지 않나?'

'그리고 이전에 스위치를 눌렀던 곳은

다시 스위치 안 누르면 되는거고'

이렇게 생각하니 문제가 간단하게 풀려서

저도 조금 당황했습니다.

'이게 왜 풀리지...?'

#백준 11967번 불켜기
from collections import deque
dx=[0,0,1,-1]
dy=[1,-1,0,0]

N,M=map(int,input().split())

switch=[[[]for _ in range(N)] for _ in range(N)]

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

    switch[x][y].append([a,b])

visited=[[False]*N for _ in range(N)]
light=[[0]*N for _ in range(N)]
q=deque()
q.append([0,0])
visited[0][0]=True
light[0][0]=1
on=[[False]*N for _ in range(N)]
while q:
    x,y=q.popleft()
    #해당지역에 스위치 on 해주기
    if switch[x][y] and on[x][y]==False:
        on[x][y]=True
        visited=[[False]*N for _ in range(N)]
        for px,py in switch[x][y]:
            light[px][py]=1
    visited[x][y]=True
    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=N or ny<0 or ny>=N:
            continue

        if light[nx][ny]==0:
            continue
        if visited[nx][ny]==True:
            continue

        q.append([nx,ny])
        visited[nx][ny]=True
answer=0
for x in range(N):
    answer+=light[x].count(1)
print(answer)

문제 정답 후

구글링해서 다른 사람들 풀이를 참고해보니

'이전에 방문한 지역을 다시 되돌린다'

라는 아이디어는 비슷했습니다.

 

한번 방문한 지역을 어떻게 방문할지에 대해서

고민하게 만들어준 좋은 문제입니다.