백준 1261번_알고스팟 (python)

 이 문제는 다익스트라알고리즘과, 0-1 너비 우선 탐색을 이용하여 풀 수 있다. 여기서는 처음 들어본 0-1 너비 우선 탐색을 다뤄보겠습니다. 0-1 너비 우선 탐색이 무엇인지 구글링을 열심히 해보고 많은 블로그들을 읽어보았지만 이해가 되지 않거나 그냥 0은 appendleft 1은 append하세요라고 언급만 하는 글들이 많아서 어려움을 겪었다.

 결국 0-1bfs 코드를 하나 가지고 여러가지 예시들을 만들어 놓고 한줄한줄 손으로 실행하면서 노트에 적어봤다. 손코딩을 해보니 0일 경우 appendleft를 해왔으니 0이 었던 좌표아거나 0인 좌표와 붙어있던 상,하,좌,우 좌표들을 우선적으로 만나게 된다.

그러다가 최종 좌표 m-1,n-1에 도착한다. (당연한 것 아니냐고 생각이 드실 수 있겠지만 저는 이 당연한 것이 이해가 안 됐습니다.....)  

아직 뭔 말인지 모르겠으신 분은 제가 올린 코드를 보시고 예시를 하나 만든 다음에 손으로 직접 한줄한줄 실행해 보시는 것을 추천드립니다.

from collections import deque
n,m = map(int,input().split())
data = []
for i in range(m):
    data.append(list(map(int,input())))
visited = [[-1] * n for i in range(m)]

dx = [1,0,-1,0]
dy = [0,1,0,-1]

def bfs(x,y):
    q = deque()
    q.append((x,y))
    visited[x][y] = 0

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if visited[nx][ny] == -1:
                if data[nx][ny] == 1:
                    q.append((nx,ny))
                    visited[nx][ny] = visited[x][y] + 1
                else:
                    q.appendleft((nx,ny))
                    visited[nx][ny] = visited[x][y]
        
bfs(0,0)
print(visited[m-1][n-1])

 

 처음 문제를 봤을 때 dfs라고 생각을 했고 길을 돌아가지 않고 최적의 길로 빠르게 갈 수 있는 방법들 중에서 백트래킹을 하면서 최소한으로 벽을 부숴야 겠다고 생각을 했다. 이 생각을 하고 나서 최대 행,열의 크기가 100*100인 것을 보고 시간초과가 나겠구나라고 생각을 했지만 그래도 혹시라는 마음을 가지고 코드를 짜봤다. 역시 행,열의 크기가 조금이라도 커지니 바로 시간초과가 났다. 그래도 날려버리기 아까워 썼던 코드를 기록해본다.

n,m = map(int,input().split())

data = []

for i in range(m):
    data.append(list(map(int,input())))

dx = [0,1]
dy = [1,0]

xcnt = n - 1
ycnt = m - 1

min_result = float("INF")
count = 0
def dfs(x,y,xcn,ycn):
    global min_result
    global count

    if xcn == n or ycn == m:
        return 

    if x == n-1 and y == m-1:
        min_result = min(min_result,count)
        return

    if data[y][x] == 1:
        count += 1

    dfs(x+1,y,xcn+1,ycn)
    dfs(x,y+1,xcn,ycn+1)
    if data[y][x] == 1:
        count -= 1

dfs(0,0,0,0)
print(min_result)