백준 31464 초콜릿 괴도 코코 (Sweet)

 

추리 소설 “초콜릿 괴도 레나”를 감명 깊게 읽은 코코는 이 소설의 명장면을 따라 해 보기로 했다. 구체적인 방법은 다음과 같다.

• 1단계: 먼저 N×N크기의 사각 격자 형태의 초콜릿을 준비한다. 이 초콜릿은 1×1 단위로 원하는 곳에서 떼어낼 수 있게 되어 있으며, 0개 이상의 단위 초콜릿이 제거된 상태이다. 이때, 남아있는 단위 초콜릿은 4개 이상이며, 한 조각을 이루어야 한다. 상하좌우로 이웃한 두 단위 초콜릿은 서로 연결되어 있으며, 서로 연결된 단위 초콜릿들의 집합을 하나의 조각이라고 한다.
• 2단계: 이 초콜릿에서 다음의 조건을 충족하도록 하나의 단위 초콜릿을 떼어 먹는다.
  • 이 단위 초콜릿을 떼어낸 후에도 남아있는 초콜릿은 하나의 조각을 이루지만, 그 이후에 서로 이웃한 임의의 두 단위 초콜릿 사이를 자르면 2개의 조각으로 나누어진다.
• 3단계: 레나의 명대사를 외친다. “이번엔 봐줬지만, 다음에는 반드시 초콜릿을 조각내 줄 거야.”

코코는 1단계의 조건을 충족하는 초콜릿을 준비해 놓았지만, 2단계의 조건을 충족하려면 어느 지점에 있는 단위 초콜릿을 떼어내야 할지 고민에 빠졌다. 코코를 도와주자.

 

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

 

 

#include <iostream>      
#include <vector>        
#include <queue>         
#include <utility>       // pair

using namespace std;

// 결과를 담을 구조체
struct ChocolateInfo 
{
    int componentCount; // 연결된 조각 개수
    int nodeCount;      // 초콜릿 조각 수
    int edgeCount;      // 연결선(간선) 수
};

int visitFlag = 0; // 현재 방문 체크용 타임스탬프
vector<vector<int>> visited; 
vector<vector<int>> direction = 
{ 
  // 방향 벡터: 우, 하, 좌, 상
  {0, 1}, {1, 0}, {0, -1}, {-1, 0} 
}; 
vector<vector<char>> chocolateMap; // 입력받은 초콜릿 맵

// 맵 범위 안에 있는 좌표인지 확인하는 함수
bool isInBounds(int n, int x, int y) 
{
    return x >= 0 && x < n && y >= 0 && y < n;
}

// BFS: 현재 맵 상태에서 조각 개수, 초콜릿 수, 간선 수 계산
ChocolateInfo bfs(int n) 
{
    ChocolateInfo result = { 0, 0, 0 };// 초기화
    queue<pair<int, int>> q;
    visitFlag++;                       // 방문 타임스탬프 갱신

    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < n; ++j) 
        {
            if (chocolateMap[i][j] == '.' || visited[i][j] == visitFlag)
                continue; // 빈 칸이거나 이미 방문했으면 패스

            result.componentCount++; // 새 조각 발견
            result.nodeCount++;      // 초콜릿 1개 포함
            visited[i][j] = visitFlag;
            q.push(make_pair(i, j)); // 시작점 큐에 추가

            while (!q.empty()) 
            {
                pair<int, int> current = q.front();
                q.pop();

                for (int d = 0; d < 4; ++d)  // 4방향 탐색
                {
                    int nx = current.first + direction[d][0];
                    int ny = current.second + direction[d][1];
					
                     // 인접한 칸이 범위 내이고 초콜릿이면
                    if (isInBounds(n, nx, ny) && chocolateMap[nx][ny] == '#') 
                    {
                        result.edgeCount++; // 연결선 증가
                        if (visited[nx][ny] < visitFlag) 
                        {
                            visited[nx][ny] = visitFlag; // 방문 표시
                            result.nodeCount++;          // 노드 수 증가
                            q.push(make_pair(nx, ny));    // 큐에 추가
                        }
                    }
                }
            }
        }
    }

    result.edgeCount /= 2; // 간선 수는 양방향이므로 2로 나눔
    return result;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
	 // 맵과 방문 배열 초기화
    chocolateMap = vector<vector<char>>(n, vector<char>(n));
    visited = vector<vector<int>>(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> chocolateMap[i][j];

    vector<pair<int, int>> result;

    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < n; ++j) 
        {
            if (chocolateMap[i][j] == '.')
                continue;  // 초콜릿이 없는 곳은 건너뜀

            chocolateMap[i][j] = '.';    // 초콜릿 하나 제거
            ChocolateInfo info = bfs(n); // 나머지 연결 상태 확인
			
            // 하나의 조각이고, 트리 구조라면 (간선 = 노드 - 1)
            if (info.componentCount == 1 && info.nodeCount - 1 == info.edgeCount)
                result.push_back(make_pair(i + 1, j + 1));  // 1-based 좌표 저장

            chocolateMap[i][j] = '#';
        }
    }

    cout << result.size() << '\n';
    for (pair<int, int> pos : result)
        cout << pos.first << ' ' << pos.second << '\n';

    return 0;
}