[백준] 16988 Baaaaaaaaaduk2 (Easy)

문제의 출처는 아래와 같다.

 

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

 

이 문제 역시 삼성 역량테스트 연습 문제이며 기출 문제의 '연구소'와 비슷한 문제이다. 내가 느끼기에는 '연구소' 보다 하위호환정도의 난이도이다.

 

이 문제는 바둑돌을 둘 수 있는 전체 경우와 각 경우에 BFS 탐색으로 조건에 맞게 실행하여 최대값을 갱신해주는 문제이다.

DFS로 전체 경우를 해도 되지만, 여기서는 다중 for문을 이용해 2개의 바둑돌을 놓을 수 있다.

2개의 바둑돌을 놓았으면 BFS를 하는데 조건에 알맞지 않으면 그 경우는 제외하여 코드를 짜면 된다.

 

 

main을 보면 4중 for문으로 이루어져 있다. 이와 같이 전체 빈 공간에 2개의 바둑돌을 놓고, BFS를 호출하여 정답을 갱신해준다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m, arr[21][21], visit[21][21], dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 }, ans, chk;
int cx[500], cy[500], k;
 
void bfs(int a, int b) {
    int E = 0, cnt = 1;
    queue<pair<int, int>> q;
    visit[a][b] = 1;
    q.push({ a,b });
    //cout << a << "   " << b << endl;
    while (!q.empty()) {
        int x, y;
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int kx, ky;
            kx = x + dx[i];
            ky = y + dy[i];
            if (kx < 0 || kx >= n || ky < 0 || ky >= m || arr[kx][ky] == 1 || visit[kx][ky] != 0) continue;
            if (arr[kx][ky] == 2 && visit[kx][ky] == 0) {
                visit[kx][ky] = 1;
                q.push({ kx,ky });
                cnt++;
            }
            if (arr[kx][ky] == 0) {
                E = 12;
            }
        }
    }
    if (E == 0) {
        //print();
        chk = chk + cnt;
        //printf("%d  \n", chk);
    }
}
 
 
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j] == 0) {
                cx[k] = i;
                cy[k] = j;
                k++;
            }
        }
    }
    for (int a = 0; a < k - 1; a++) {
        for (int b = a + 1; b < k; b++) {
            arr[cx[a]][cy[a]] = arr[cx[b]][cy[b]] = 1;
 
 
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (arr[i][j] == 2 && visit[i][j] == 0) {
                        bfs(i, j);
                        //printf("\n");
                    }
                }
            }
            //print();
            //printf("\n\n");
            arr[cx[a]][cy[a]] = arr[cx[b]][cy[b]] = 0;
            ans = max(ans, chk);
            chk = 0;
            memset(visit, 0, sizeof(visit));
        }
    }
    printf("%d", ans);
    return 0;
}