백준: 11048 이동하기

문제

11048번: 이동하기

 

문제 풀이

 N X M의 미로가 주어질 때, 현재 위치에서 (1, 0), (0, 1), (1, 1)과 같은 경로로 이동할 수 있다. 왼쪽 가장 윗방에서 출발하여, 가장 오른쪽 끝인 N, M에 도착할 때 최대로 가져올 수 있는 사탕의 개수를 반환하면 된다.

 

 문제를 풀기 위해서는 입력받은 그래프에 추가적으로 데이터를 줄 필요가 있다. 예를 들어 예제 입력 2는 다음과 같이 변환할 수 있다. 

 

  기존의 그래프를 위와 같이 변경하면 점화식 `graph[i][j] += max(graph[i - 1][j], graph[i][j - 1], graph[i - 1][j - 1])`을 통해 문제의 답을 찾을 수 있다.

 

 예제 입력 2의 정답을 찾는 과정은 위의 점화식과 같이 현재 위치에서 반영하고자 하는 값을 선택하여 N, M이 되었을 때 3이라는 값을 찾을 수 있다.

 

코드

점화식을 이용한 풀이

from sys import stdin


if __name__ == "__main__":
    n, m = map(int, stdin.readline().split())
    graph = [[0] + list(map(int, stdin.readline().split())) for _ in range(n)]
    graph.insert(0, [0] * (m + 1))

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            graph[i][j] += \
                max(graph[i][j - 1], graph[i - 1][j], graph[i - 1][j - 1])

    print(graph[n][m])

 

BFS를 이용한 풀이

from sys import stdin
from collections import deque


def visitable(x, y):
    return 0 <= x < n and 0 <= y < m


def bfs(start):
    q = deque([start])
    visited[0][0] = graph[0][0]

    while q:
        cur_x, cur_y = q.popleft()

        for x, y in ((1, 0), (0, 1), (1, 1)):
            next_x, next_y = cur_x + x, cur_y + y

            if visitable(next_x, next_y):
                sum_candy = visited[cur_x][cur_y] + graph[next_x][next_y]
                if visited[next_x][next_y] < sum_candy:
                    visited[next_x][next_y] = sum_candy
                    q.append([next_x, next_y])

    return visited[-1][-1]

if __name__ == "__main__":
    n, m = map(int, stdin.readline().split())
    visited = [[-1] * m for _ in range(n)]
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    print(bfs([0, 0]))

 visited를 방문 했을 때, 사탕의 개수가 반영되도록 하면 BFS를 통해서도 답을 찾을 수 있다. 하지만 당연하게도 BFS가 DP보다 상대적으로 느리다.