[백준 2423번] 전구를 켜라 (Python3)

import sys,collections
input = sys.stdin.readline
dy = [1,1,-1,-1]; dx = [1,-1,-1,1]

def BFS():
  if (N+M)%2:
    return "NO SOLUTION"
  visited = [[0]*(M+1) for i in range(N+1)]
  dq = collections.deque([(0,0,0)])
  while dq:
    y,x,d = dq.popleft()
    if visited[y][x]:
      continue
    visited[y][x] = 1
    if y==N and x==M:
      return d
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>=y1>=0 and M>=x1>=0 and not visited[y1][x1]:
        if not (i+board[y-int(dy[i]<0)][x-int(dx[i]<0)])%2:
          dq.appendleft((y1,x1,d))
        else:
          dq.append((y1,x1,d+1))
  
N,M = map(int,input().split())

board = [[*map(lambda x:1 if x=="/" else 0,input().strip())] for i in range(N)]
print(BFS())

처음에는 다익스트라로 해결하려 하였다.

경로가 이미 존재하면 거리 0, 아니면 거리 1로 두고 모든 좌표에 대해서 다익스트라로 최단거리를 찾으려 했는데, 아무리 상수커팅을 해줘도 시간초과를 피할 수 없었다.

 

그렇게 어떻게 시간을 줄일까 고민하던 중, "거리가 0인 경우에는 appendleft, 거리가 1인 경우에는 append를 해주면 되겠구나" 하는 방법이 생각났다.

즉, BFS를 실행하면서 이미 경로가 존재하는 경우에는 deque의 왼쪽에 삽입하고, 아닌 경우에는 deque의 오른쪽에 d+1로 삽입하는 방식이다. BFS의 경우 거리순으로 탐색을 해야하는데, 거리가 0인 경우에는 거리가 같기 때문에 사용할 수 있는 방식이다.

 

따라서 풀이를 정리하면,

1. N+M이 2의 배수가 아니라면 NO SOLUTION을 출력한다.

2. 1에 해당하지 않는 경우, BFS로 모든 지점을 탐색한다. 이때 이미 경로가 존재하는 경우 deque의 왼쪽에, 아닌 경우 오른쪽에 삽입한다.

3. N,M에 도착하면 결과를 출력한다.

 

 

그런데 내 방식이 사실은 0-1 BFS라는 알고리즘이라고 한다. 이미 존재하는 알고리즘이라고 하니 약간 허무하기도 하고 한편으로는 이걸 혼자 생각해냈다는 사실이 뿌듯하기도 했다.

 

 

여담) 이 문제 숏코딩 순위 1위가 되었다.