0-1 BFS를 처음 성공한 날.

저번 포스팅 중에서 0-1 BFS를 공부할 필요가 있다고 했었다.

근데 오늘 자연스럽게 해버림

 

#1261  알고스팟 https://www.acmicpc.net/problem/1261

1261번: 알고스팟

처음엔 그냥 DP를 사용한 BFS로 풀이했다.

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

way = [[int(x) for x in input()] for _ in range(M)]
visited = [[-1 for _ in range(N)] for __ in range(M)]

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

que = [[0, 0]]
visited[0][0] = 0
while que:
    x, y = que.pop(0)

    walls = visited[x][y]

    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < M and 0 <= ny < N:
            # print(nx, ny)
            if visited[nx][ny] == -1:
                visited[nx][ny] = walls + way[nx][ny]
                que.append([nx, ny])
            else:
                visited[nx][ny] = min(walls + way[nx][ny], visited[nx][ny])
                que.append([nx, ny])

print(visited[M-1][N-1])

틀리는 이유를 알 수 없었다.

 

구글링 결과

문제는 역시 가중치의 차이에서 발생했다.

1인 노드에서는 1을 더해주고

0인 노드에서는 0을 더해준다.

 

때문에 같은 길이였어도 가중치가 1인 노드를 지나온 경로가 더욱 큰 값을 갖는다.

나는 이를 처리하기 위해 min을 적용했었다.

근데 필요없었다.

 

가중치가 더 작은 노드를 지나는 경로라면

BFS탐색의 que에서 leftappend를 해주면 된다.

즉 가중치가 0인 노드를 만날 경우를 우선해서 연산하는 것이다.

 

이를 0-1 BFS라고 한다.

 

수정 후 시간초과가 나지 않은 코드

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

way = []
for i in range(N):
    way.append(list(map(int, input())))
visited = [[-1]*M for i in range(N)]

# 상하좌우 탐색
dx = [1,  0, 0, -1]
dy = [0, 1, -1, 0]

que = [[0, 0]]
visited[0][0] = 0
while que:
    x, y = que.pop(0)

    walls = visited[x][y]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < N and 0 <= ny < M:
            # print(nx, ny)
            if visited[nx][ny] == -1:
                if way[nx][ny] == 0: #가중치가 0인 경우
                    visited[nx][ny] = walls + way[nx][ny]
                    # left append
                    que = [[nx, ny]] + que
                   
                else: # 가중치가 0이 아닌경우 (1인경우)
                    visited[nx][ny] = walls + way[nx][ny]
                    # right append
                    que.append([nx, ny])


print(visited[N-1][M-1])

 

배운게 많은 문제였다.