[백준] 18290번 NM과 K (1) (C++) - backtracking

문제

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

18290번: NM과 K (1)

코드

#include <iostream>

using namespace std;

int arr[11][11];
int isVisited[11][11];

int maxN = -40000;
int n,m,k;

void dfs(int y, int x, int cnt, int sum){
  sum+=arr[y][x];
  cnt++;
  if(cnt==k){
    if(sum>maxN) maxN = sum;
    return;
  }

  isVisited[y][x]++;
  if(y-1>0) isVisited[y-1][x]++;
  if(y+1<=n) isVisited[y+1][x]++;
  if(x-1>0) isVisited[y][x-1]++;
  if(x+1<=m) isVisited[y][x+1]++;

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      if(isVisited[i][j]==0){
        dfs(i, j, cnt, sum);
      }
    }
  }

  isVisited[y][x]--;
  if(y-1>0) isVisited[y-1][x]--;
  if(y+1<=n) isVisited[y+1][x]--;
  if(x-1>0) isVisited[y][x-1]--;
  if(x+1<=m) isVisited[y][x+1]--;
}

int main(){
  cin >> n >> m >> k;
  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      cin >> arr[i][j];
    }
  }

  for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
      dfs(i, j, 0, 0);
    }
  }

  cout << maxN;
  return 0;
}

정리

처음에 isVisited배열을 bool로 선언해서 시간을 많이 잡아먹었던 문제다.

5 5 3

0 0 0 0 0
0 9 0 9 0
10 0 9 0 0
0 0 0 1 0
0 0 0 0 0

isVisited를 bool로 선언했을 경우 나올 수 있는 반례가 위 예시이다. 문제대로라면 9+9+10으로 28이 나와야 하지만 isVisited를 bool로 선언했을 경우에는 29가 나온다. 29는 10+10+9로 나온 결과이다. 이것은 선택한 칸들이 공통적으로 방문할 수 없는 경우를 고려하지 않아서 생긴 문제이다. 10을 처음에 방문처리를 했더라도 어떤 경우의 수에 의해 10의 방문처리가 false로 바뀌어 다시 10을 접근할 수 있다. 이 문제를 해결하기 위해서는 isVisited를 int로 선언하고 isVisited가 0인 경우에만 방문할 수 있도록 코드를 구현하면 해결할 수 있다.

참조