파이썬 백준 1261번 : 알고스팟

문제

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

 

 

풀이

알고리즘

BFS

자료구조

리스트(인접행렬)

 

import sys
from collections import deque
def BFS():
    queue=deque()
    queue.append((0,0,0))
    while queue:
        x,y,b=queue.popleft()
        for i in range(4): #상,하,좌,우 탐색
            n_x=x+dx[i]
            n_y=y+dy[i]
            if 0<=n_x<M and 0<=n_y<N:
                if maps[n_x][n_y]==1 and b+1<visited[n_x][n_y]: #벽이고 해당 좌표의 visited값이 b+1보다 클때
                    queue.append((n_x,n_y,b+1)) # 값 업데이트 및 queue에 넣기
                    visited[n_x][n_y]=b+1
                elif maps[n_x][n_y] == 0 and b<visited[n_x][n_y]: #벽이 아니고  해당 좌표의 visited값이 b보다 클때
                    queue.append((n_x, n_y, b)) # 값 업데이트 및 queue에 넣기
                    visited[n_x][n_y] = b

N,M=map(int,sys.stdin.readline().split())
maps=[]
dx=[1,-1,0,0]
dy=[0,0,-1,1]
visited=[] #부셔야하는 벽의 개수가 저장됨(최대로 초기화)
for i in range(M): # maps과 visited 배열 생성
    maps.append(list(map(int,sys.stdin.readline().strip())))
    visited.append([200]*N)

BFS() #BFS실행 -> visited 업데이트
if N==M==1: #1 1 0 일경우 반례처리
    print(maps[0][0])
else:
    print(visited[M-1][N-1])

 

 

덧)

100%에서 틀려 반례를 찾기 어려웠다.

visited 처리의 위치가 위에서 이루어지면 틀리던데 잘 모르겠다.. 다음에 다시 풀어볼문제