#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<int>> candy_map(N, vector<int>(M));
    vector<vector<int>> dp(N, vector<int>(M));

    // 사탕 맵 입력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> candy_map[i][j];
        }
    }

    // DP 초기화
    dp[0][0] = candy_map[0][0];

    // 첫 번째 행 초기화
    for (int j = 1; j < M; j++) {
        dp[0][j] = dp[0][j-1] + candy_map[0][j];
    }

    // 첫 번째 열 초기화
    for (int i = 1; i < N; i++) {
        dp[i][0] = dp[i-1][0] + candy_map[i][0];
    }

    // 나머지 DP 테이블 채우기
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
            dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + candy_map[i][j];
        }
    }

    // 결과 출력
    cout << dp[N-1][M-1] << endl;

    return 0;
}

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;

int N, M;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int bfs(vector<vector<int>>& map) {
    vector<vector<vector<int>>> visited(N, vector<vector<int>>(M, vector<int>(2, 0)));
    queue<tuple<int, int, int>> q; // (x, y, 벽 부쉈는지 여부)
    
    q.push({0, 0, 0});
    visited[0][0][0] = 1;

    while (!q.empty()) {
        int x, y, wall;
        tie(x, y, wall) = q.front();
        q.pop();

        if (x == N-1 && y == M-1) {
            return visited[x][y][wall];
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                // 벽이 없는 경우
                if (map[nx][ny] == 0 && visited[nx][ny][wall] == 0) {
                    visited[nx][ny][wall] = visited[x][y][wall] + 1;
                    q.push({nx, ny, wall});
                }
                // 벽이 있는 경우
                if (map[nx][ny] == 1 && wall == 0 && visited[nx][ny][1] == 0) {
                    visited[nx][ny][1] = visited[x][y][wall] + 1;
                    q.push({nx, ny, 1});
                }
            }
        }
    }

    return -1;
}

int main() {
    cin >> N >> M;
    vector<vector<int>> map(N, vector<int>(M));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }

    cout << bfs(map) << endl;

    return 0;
}

유니티 공부

10강 유니티 뮤즈