[백준] 14502번 연구소

14502번: 연구소

이 문제는 브루트 포스 + bfs or dfs로 푸는 문제다. 

 

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int maps[30][30];
int dist[30][30];
bool visit[30][30];
int N,M;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};
int bfs() {
  queue<pair<int,int>> q;
  for(int i = 0; i<N;i++) {
    for(int j = 0; j <M;j++) {
      dist[i][j] = maps[i][j];
      if (dist[i][j] == 2) {
        q.push({i,j});
        visit[i][j] = true;
      }
    }
  }

  while(!q.empty()) {
    auto c = q.front(); q.pop();

    for(int i = 0; i<4;i++) {
      int nx = c.X + dx[i];
      int ny = c.Y + dy[i];

      if (nx <0 || N <= nx || ny < 0 || M <= ny) continue;
      if (dist[nx][ny] != 0) continue;
      q.push({nx,ny});
      dist[nx][ny] = 2;
      visit[nx][ny] = true;

    }
  }
  int cnt = 0;
  for(int i = 0;i<N;i++) {
    for(int j = 0; j<M;j++) {
      if (dist[i][j] == 0) {
        cnt++;
      }
    }
  }
  return cnt;
}

int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  
  cin >> N >> M;

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


  int ans = 0;

  for(int x1 = 0; x1<N;x1++) {
    for(int y1 = 0; y1<M;y1++) {
      if (maps[x1][y1] != 0) continue;

        for(int x2 = 0; x2 < N;x2++) {
          for(int y2 = 0; y2 < M;y2++) {
            if (maps[x2][y2] != 0) continue;
              for(int x3 = 0; x3 < N;x3++) {
                for(int y3 = 0; y3 <  M;y3++) {
                  
                  if (maps[x3][y3] != 0) continue;
                  if (x1 == x2 && y1 == y2) continue;
                  if (x1 == x3 && y1 == y3) continue;
                  if (x2 == x3 && y2 == y3 ) continue;

                  maps[x1][y1] = 1;
                  maps[x2][y2] = 1;
                  maps[x3][y3] = 1;
                  ans = max(ans,bfs());
                  maps[x1][y1] = 0;
                  maps[x2][y2] = 0;
                  maps[x3][y3] = 0;
                }
              }
          }
        }
    }
  }

  cout <<  ans << "\n";


} 

솔직히 마음에 들지 않아 재귀를 사용하고 싶지만... 현재 재귀를 잘 사용하지 못해서 ㅜㅜ 일단 6중 포문을 사용해서 해결했다.

 

다른 bfs문제들은 한번 만 bfs를 돌리면 될지도 모르지만... 이 문제는 계속 돌려야 한다. 왜냐하면 연구소안에 벽을 세우는데 그 벽을 정확히 어디에 세우는지 모르기 때문이다. 그래서 브루트포스를 이용해서 모든 경우의 수를 계산해줘야한다. 

예륻들어

이런 코드가 있다고 가정하자. 그러면 모든 0에 벽을 세울 수 있다. 아까도 말했듯이 벽을 정확히 어디에 세우는지 모른다. 아니 계산할 수 없다. 

그래서 

2 1 1 1 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

2 0 0 1 1 1 0
0 0 1 1 1 2 0
0 1 1 1 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이런식으로 검사를 다 해줘야한다. 물론 방법이야 있을 수 는 있겠지만 현재의 배운걸로는 모르겠다.  

아무튼... 이렇게 계산한 내용들을 bfs혹은 dfs를 이용해서 해결하면 된다.

 

근데 의문이 드는 부분이 2군데 있었다.

하나는 dist[i][j] = maps[i][j]하는 이유는?

maps[i][j] != 0  continue 시리즈 이유...

 

첫번째꺼는 더이상 maps를 더럽히지 않기 하기 위해서다. 그 이유는 bfs코드를 보면 알 수 있는데

값을 2로 바꾸는 코드를 확인 할 수 있다. 그래서 다른걸로 대신해서 더럽히고 그것으로 계산하는 거다.

 

두 번째꺼는 그냥 벽을 세울때 0만 가능하기 때문에 0이 아닌 값들은 전부 무시하는 전략을 같기 위해서다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    
    static class Pair {
        int x;
        int y;
        
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    
    static int n, m;
    static int[][] map;
    static int[][] copy;
    
    static int ans = 0;
    
    ArrayList<Pair> vlist = new ArrayList<>();
    
    
    static void CopyMap() {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                copy[i][j] = map[i][j];
            }
        }
    }
    
    
    static int getSafeArea() {
        int cnt = 0;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if (copy[i][j] == 0) cnt++;
            }
        }
        
        return cnt;
    }
    
    
    static void spreadVirus(int x, int y) {
        for(int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                if(copy[nx][ny] == 0) {
                    copy[nx][ny] = 2;
                    spreadVirus(nx, ny);
                }    
            }
        }
    }
    
    
    static void setWall(int start, int depth) {
        if(depth == 3) {
            copyMap();
            
            for(Pair p : vlist) {
                spreadVirus(p.x, p.y);
            }
            
            ans = Math.max(ans, getSafeArea());
            
            return;
        }
        
        for(int i = start; i < n * m; i++) {
            int x = i / m;
            int y = i % m;
            
            if(map[x][y] == 0) {
                map[x][y] = 1;
                setWall(i + 1, depth + 1);
                map[x][y] = 0;
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        map = new int[n][m];
        copy = new int[n][m];
        
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 2) {
                    vlist.add(new Pair(i, j));
                }
            }
        }
        
        setWall(0, 0);
        System.out.println(ans);
    }
}

코드는 자바지만... 나는 c++풀었지만. 언어가 다르지만...