Editorial for [sw] 최대 점수를 얻어보자

이 해설은 꼭 필요할 때만 사용하고, 코드를 복사-붙여넣기 하지 마세요. 문제 출제자와 해설 작성자를 존중해 주세요.
문제를 직접 풀기 전에 공식 해답을 제출하는 것은 제재 대상입니다.

태그

브루트포스 DFS

정답 코드

#include <bits/stdc++.h>

using namespace std;

int N, K;
int result = -100000000;
int board[10][10];
bool visited[10][10];

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

void dfs(pair<int, int> cur, int val, int cnt) {
    if(cnt == K) {
        result = max(result, val);
        return;
    }

    for(int dir = 0; dir < 4; ++dir) {
        int x = cur.first + dx[dir];
        int y = cur.second + dy[dir];
        if(x < 1 || x > N || y < 1 || y > N || visited[x][y]) continue;
        visited[x][y] = true;
        dfs({x, y}, val + board[x][y], cnt + 1);
        visited[x][y] = false;
    }
}

int main() {
    cin>>N>>K;
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            cin>>board[i][j];
        }
    }

    visited[1][1] = true;
    dfs({1, 1}, board[1][1], 1);

    cout<<result;

    return 0;
}

댓글

현재 작성된 댓글이 없습니다.