[99클럽 코테 스터디 20일차 TIL + dfs/bfs] 백준 17265 나의 인생에는 수학과 함께 파이썬

오늘의 학습 키워드

dfs+bfs

공부한 내용 본인의 언어로 정리하기

문제

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

 

코드

from collections import deque

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(input().split()))

answer = []
t = int(arr[0][0])
def bfs(x, y, t, op):
    q = deque()
    q.append((x, y, t, op))
    while q:

        x, y, t, op = q.popleft()
        for a, b in [(1, 0), (0, 1)]:
            nx, ny = x + a, y + b
            if nx >= n or ny >= n:
                continue

            if arr[nx][ny] in '+-*':
                q.append((nx, ny, t, arr[nx][ny]))

            else:
                a = int(arr[nx][ny])
                if op == '+':
                    nt = t + a
                elif op == '-':
                    nt = t - a
                else:
                    nt = t * a
                q.append((nx, ny, nt, ''))

            if nx == n-1 and ny == n-1:
                answer.append(nt)

bfs(0, 0, t, '')
print(max(answer), min(answer))

 

bfs로 모든 경로를 탐색해서 구할 수 있는 모든 결과값을 담아주고 이후 max랑 min을 통해 최댓값, 최소값을 구해주었다. 기본적으로 한 경로에 대한 깊이 탐색이 아니라 갈 수 있는 모든 길을 탐색해야 함으로 bfs를 선택했고, bfs 함수에는 x, y, 현재 계산값인 t, 현재 부호인 op를 넘겨주었다. q에 있는 값을 돌면서 갈 수 있는 방향인 아래쪽, 위쪽 두 개를 돌며 새로운 nx, ny 값을 갱신하며 arr[nx][ny]에 있는 값을 검사한다.

만일 현재 값이 부호이면 현재 부호값을 op값에 갱신하여 q에 새로 넣어주고, 만일 현재 값이 숫자라면 이전에 저장했었던 op값을 검사하여 해당 값에 따라 검사한다. 이때 t는 기존 t에 갱신하지 말고 새로운 t에 계산해주어야 한다. 이후 계산한 값도 당연히 q에 넣어준다. 

nx, ny가 지도 끝에 도착했다면, 해당 nt값을 answer에 넣어준다. 다 계산하고 나면, max값과 min값을 출력한다. 

오늘의 회고

처음에는 부호를 처리할 줄 몰라서 헤멨고, 그 후에는 bfs에 넣는 값을 어디까지 넣어야 하는지 헷갈려서 헤멧고, 마지막으로 계산한 t값을 append를 해주지 않아 헤멨다. 그래도 이제 bfs에 익숙해진 것 같아서 기분이 좋다.