백준 - 11048번, 이동하기 문제 BFS및 Dynamic programming 풀이 (C++)

이번에 풀이해본 문제는 11048번 이동하기 문제로, solved.ac 기준 실버 2 난이도의 문제입니다.

 

요즘 들어 ps를 너무 오랫동안 방치해서 감을 살릴 겸 기본적인 예제가 없을까 하다가 적당한 난이도의 문제가 보여서 풀게 되었습니다.

 

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

11048번: 이동하기

문제 설명부터 정리한 이후 제 풀이 과정에 대해서 정리해 보겠습니다!

---

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

---

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

---

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

---

나의 풀이 과정 정리

우선 문제의 유형은 "미로를 세 가지 방향으로 탐색하면서, 최대로 주울수 있는 사탕의 개수를 센다? => BFS 방식으로 탐색하면서 DP를 적용하면 풀리겠다."라는 생각을 통해 파악할 수 있었습니다.

 

따라서 처음에는 BFS 방식의 그래프 탐색을 구현하기 위해 queue 자료 구조를 활용해 해당 위치에서 보유한 최대 사탕 개수가 갱신되는 경우에 대해서만 queue에 push 하여 이어서 최대 사탕의 개수에 대해 그 위치에서 탐색하는 방식으로 풀이했습니다.

하지만, 이렇게 풀이하는 경우에는 그 시점에 대해서만 최댓값을 탐색하게 되는, 어찌보면 그리디스럽게? 탐색을 진행하게 되어 일부의 경우에 대해서 최대 사탕의 개수를 탐색하는데 실패하여 96퍼센트에서 계속해서 오답처리가 되었던 것 같습니다.

이 부분을 보완하기 위해서 queue의 사용을 배제하고, 2중 for문을 활용해 전체 미로의 칸에서 전개 가능한 방향에 대해 최댓값을 갱신하는 방식으로 코드를 수정하여 정답 처리를 받을 수 있었습니다.

 

if d[x][y] + 현재 캔디 > d[next x][next y]
‌d[next x][next y] = d[x][y] + 현재 캔디

참고로 각 칸에서 최대 캔디의 갱신은 위의 슈도 코드와 같은 방식으로 갱신했습니다.

 

---

제출 코드

#include <iostream>
#include <queue>
#define MAX 1001 

using namespace std;

int n, m;

int d[MAX][MAX];
int map[MAX][MAX];

bool inRange(int x, int y) {
‌return 1 <= x && x <= n && 1 <= y && y <= m;
}

void bfs() {
‌// 하, 우, 우하
‌int dx[] = {1, 0, 1};
‌int dy[] = {0, 1, 1};

‌d[1][1] = map[1][1];

‌for(int x = 1; x <= n; x++){
‌‌for (int y = 1; y <= m; y++) {
‌‌‌for (int i = 0; i < 3; i++) {
‌‌‌‌int nx = x + dx[i];
‌‌‌‌int ny = y + dy[i];

‌‌‌‌// 미로를 벗어나는 경우는 탐색하지 않는다.
‌‌‌‌if (!inRange(nx, ny))
‌‌‌‌‌continue;

‌‌‌‌int candy = map[nx][ny];

‌‌‌‌if (d[x][y] + candy > d[nx][ny]) {
‌‌‌‌‌d[nx][ny] = d[x][y] + candy;
‌‌‌‌}
‌‌‌‌else {
‌‌‌‌‌continue;
‌‌‌‌}
‌‌‌}
‌‌}
‌}

‌return;
}

int main() {
‌ios::sync_with_stdio(false);
‌cin.tie(NULL);
‌cout.tie(NULL);

‌cin >> n >> m;

‌for (int i = 1; i <= n; i++) {
‌‌for (int j = 1; j <= m; j++) {
‌‌‌cin >> map[i][j];
‌‌}
‌}

‌bfs();
‌cout << d[n][m];
‌return 0;
}

/*
오른쪽, 아래쪽, 대각선 우측 하단
세 가지 방향으로만 이동할 수 있다.

*/