2665 미로만들기

www.acmicpc.net/problem/2665

2665번: 미로만들기

 

bfs 심화문제에도 있었던 문제인데, bfs템플릿에다가 다익스트라를 섞어서 푸는 문제이다.

 

모든곳을 INF로 초기화시킨 dp배열을 만들고

 

모든곳을 탐색하면서 검은색이면 +1했을때 더 크면 진입해서 작게만들고 흰색방이면 그냥 더 클때 진입해서 값을 작게 만들어준다.

 

그렇게 되면 dp에는 해당 지점에서 검은색방을 바꿔서 도달할 수 있는 최소값을 갖게 되며,

 

dp[n-1][n-1]에는 최종 결과값이 들어가게 된다.

 

주의할점은 dp를 초기에 INF로 초기화를 시키는데, 시작전에 dp[0][0] = 0를 해주어야 정상적인 실행이 된다. 실수하지말자!

 

import sys
input = sys.stdin.readline

from collections import deque

n = int(input().rstrip())
board = [] # 미로
dp = [] # 흰방으로 바꾼 개수 누적
INF = int(1e9)
for _ in range(n):
    board.append( list(map(int,list( input().rstrip() ) ) ) )
    dp.append( [INF]*n )
    

def bfs():
    global n, board, visited, dp
    # 상하좌우
    x_direction=[-1,1,0,0]
    y_direction=[0,0,-1,1]
    
    q = deque()
    q.append((0,0))
    dp[0][0]=0
    
    while(len(q) != 0):
        
        x,y = q.popleft()

        for i in range(4):
            new_x, new_y = x+x_direction[i], y+y_direction[i]
            
            if( new_x >= 0 and new_y>=0 and new_x<n and new_y<n ): # 유효범위 내에 있는지 체크
                
                if( board[new_x][new_y] == 0 ): # 검은벽
                  if(dp[new_x][new_y] > dp[x][y]+1): # 더 큰값이면 이동해서 작게 만들어준다.
                    dp[new_x][new_y] = dp[x][y]+1
                    q.append((new_x, new_y))
                else: # 하얀벽
                    if(dp[new_x][new_y] > dp[x][y]): # 더 큰값이면 이동해서 작게 만들어준다.
                        dp[new_x][new_y] = dp[x][y]
                        q.append((new_x, new_y))
    
bfs()
print(dp[n-1][n-1])
# for i in dp:
#   print(" ".join(map(str,i)))