[BOJ] 알고스팟 1261 ★

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

 

1. 문제 이해 및 해결과정

- Floodfill 대로 BFS를 쓰되, 최단거리를 저장할 때 0이면 거리가 0더해지고 1이면 1더하면 최적의 경로에 1의 개수가 몇개인지 구할 수 있다.  - 우선순위를 높이기 위해서 0이라면 왼쪽으로 append하여 우선순위를 높였다.

-입력이 붙어있을 때 아래코드로 하면된다. 

board = [list(map(int, input())) for _ in range(n)] #붙어있는 입력 받기

: input=sys.stdin.readline 때문에 오류가 났었다. 입력이 붙어있을경우, 이 코드를 쓰면 안된다.  

 

2. 풀이방법

 1.  가중치가 다른 BFS  

#알고스팟
#https://www.acmicpc.net/problem/1261
#최적의 경로에 1의 개수가 몇개인가?
import sys
from collections import deque
sys.stdin = open("input.txt","r")
#input=sys.stdin.readline
m,n=map(int,input().split()) #가로, 세로
board = [list(map(int, input())) for _ in range(n)] #붙어있는 입력 받기
visited = [[0]*(m) for _ in range(n)]

dh=[-1,1,0,0]
dw=[0,0,-1,1]
Q=deque()
Q.append((0,0))
visited[0][0]=1
while Q:
    h,w=Q.popleft()
    if h==n-1 and w==m-1 :
        break
    for i in range(4):
        nh=h+dh[i]
        nw=w+dw[i]
        if 0<=nh<n and 0<=nw<m and visited[nh][nw]==0:
            if board[nh][nw]==0:
                Q.appendleft((nh,nw))
                visited[nh][nw]=visited[h][w]
            else :
                Q.append((nh, nw))
                visited[nh][nw] = visited[h][w] + 1

print(visited[n-1][m-1]-1)

 

3. 오답원인

-visited[0][0]을 안해주면 오류가난다. 체크가 안되니까 . 

 

4. 알게된 점

띄어쓰기가 없는 input 입력받기

board = [list(map(int, input())) for _ in range(n)]