BFS 응용문제(이코테)

날짜 : 2022. 10.08. 

사용 언어 : python

 

문제

 

코드

from collections import deque
import sys

def bfs(x, y, num):
    #print("%d %d :"%(x, y), end=' ')
    if x >= n or y >= m: # 도착점에 도달 or 범위 이탈
        # print("범위 이탈")
        return
    elif x == (n-1) and y == (m-1):
        graph[x][y] = num
        return
    if graph[x][y] == 0:
        # print("값이 0")
        return
    else:
        # print("%d"%(graph[x][y]))
        graph[x][y] = num
        bfs(x+1, y, num+1)
        bfs(x, y+1, num+1)
    return

# 좌표의 개수 입력
n, m = map(int, sys.stdin.readline().split())
graph = []

# 그래프 입력
for i in range(n):
    graph.append(list(map(int, input())))

bfs(0, 0, 1)
print(graph[n-1][m-1])
for i in graph:
    print(i)

 

 

알게된 점

- x-1, y-1의 경우의수는 고려하지 않아도 됐다.

- 입력방식에서 공백이 주어지냐 주어지지 않느냐 또한 고려대상이기 때문에 input을 쓸지, sys.stdin.readline()을 사용할지 잘 선택해야 할 것 같다.

 

 

참고 사이트

-