백준 16197 c++ "두 동전" -PlusUltraCode-

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

[필자 사고]

단순 구현 문제다. 필자는 처음에 이동하려는 칸에 동전이 있는 경우는 어떻게 해야 될지 고민했는데

문제에서 한 칸 이동한다고 되어 있다. 즉 겹쳐도 된다는 소리다.

갑자기 문제 난이도가 훅 줄어들었다.

 

방문처리는 4차원 배열 visited를 이용하여 방문 처리를 진행해 주었따.

ㅇㅏ래는 자세한 코드 해설이다.

[코드 해설]

1. main() 함수

프로그램의 시작점으로, 입력 처리와 탐색 실행을 담당한다.

• cin >> N >> M 으로 보드의 세로(N)와 가로(M) 크기를 입력받는다.
• 이후 for문을 통해 보드의 상태를 입력받는다.
  • '#'는 벽, '.'은 빈 칸, 'o'는 동전의 위치를 의미한다.
• 두 개의 동전 좌표를 각각 a, b에 저장하고, 보드 상에서는 '.'로 바꾼다.
  이렇게 하는 이유는 이후 BFS에서 동전이 빈 칸처럼 이동하도록 만들기 위해서다.
• 입력이 끝나면 BFS(a, b) 함수를 호출하고, 반환값(최소 이동 횟수 또는 -1)을 출력한다.

---

2. BFS() 함수

이 함수는 너비 우선 탐색을 이용해 모든 가능한 상태를 탐색하며,
두 동전 중 하나만 떨어지는 최소 이동 횟수를 계산한다.

(1) 매개변수

• pair<int,int> a, b: 두 동전의 초기 좌표

(2) 초기 설정

• queue<Coin> q: BFS 탐색을 위한 큐.
  Coin 구조체는 두 동전의 좌표(y1,x1, y2,x2)와 이동 횟수(count)를 저장한다.
• 초기 상태를 큐에 넣고, 해당 상태를 visited 배열에 표시한다.

(3) 탐색 반복

큐가 빌 때까지 다음을 반복한다.

1. 현재 상태를 꺼냄
   • now.count가 10 이상이면 문제의 조건상 실패이므로 -1을 반환한다.
2. 4방향으로 이동 시도
   • dy, dx 배열을 이용해 위, 아래, 왼쪽, 오른쪽 방향으로 동시에 이동을 시도한다.
   • 각각의 코인에 대해 새로운 좌표 (ny1, nx1)과 (ny2, nx2)를 계산한다.
3. 보드 밖 판정
   • board[ny1][nx1] == false 또는 board[ny2][nx2] == false 조건을 통해
     두 동전 중 하나라도 보드 밖으로 나갔는지 판정한다.
   • 두 동전이 모두 밖으로 떨어졌다면 현재 이동은 무효(continue).
   • 단 하나의 동전만 떨어졌다면 now.count + 1을 반환하여 탐색 종료.
4. 벽 충돌 처리
   • 이동하려는 칸이 벽(#)이면, 해당 코인은 원래 위치로 되돌린다.
   • 즉, ny -= dy[i]; nx -= dx[i]; 로 한 칸 뒤로 이동시킨다.
5. 방문 여부 확인
   • visited[ny1][nx1][ny2][nx2]가 false라면,
     아직 탐색하지 않은 상태이므로 큐에 넣고 방문 표시를 한다.
6. 큐 반복 종료 조건
   • 모든 가능한 상태를 탐색했음에도 한 동전만 떨어지는 경우가 없다면 -1을 반환한다.

---

3. isInside() 함수

현재 좌표가 보드 내부에 존재하는지를 판별하는 단순한 유틸리티 함수다.

• 인자로 받은 (y, x)가
  0 ≤ y < N, 0 ≤ x < M 을 만족하면 true를 반환한다.
• 보드 범위를 벗어나면 false를 반환한다.
• 동전이 떨어졌는지를 확인할 때 활용된다.

---

4. visited 배열

visited[21][21][21][21]은 두 동전의 좌표 조합을 모두 관리하기 위한 4차원 배열이다.
이는 “첫 번째 동전이 (y1,x1)에 있고, 두 번째 동전이 (y2,x2)에 있을 때”의 상태가
이미 탐색된 적이 있는지를 저장하는 역할을 한다.
즉, 동일한 두 동전의 상대적 위치 조합은 한 번만 탐색하도록 하여 중복 탐색을 방지한다.

---

5. Coin 구조체

하나의 BFS 상태를 표현한다.

• y1, x1: 첫 번째 동전의 좌표
• y2, x2: 두 번째 동전의 좌표
• count: 현재까지 버튼을 누른 횟수

이 구조체 덕분에 각 BFS 상태에서 두 동전의 위치와 이동 횟수를 함께 관리할 수 있다.

[소스 코드]

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N, M;
char board[21][21];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

struct Coin {
    int y1, x1, y2, x2, count;
};

bool visited[21][21][21][21];

bool isInside(int y, int x) {
    return (y >= 0 && y < N && x >= 0 && x < M);
}

int BFS(pair<int, int> a, pair<int, int> b) {
    queue<Coin> q;
    q.push({ a.first, a.second, b.first, b.second, 0 });
    visited[a.first][a.second][b.first][b.second] = true;

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

        if (now.count >= 10) return -1;

        for (int i = 0; i < 4; i++) {
            int ny1 = now.y1 + dy[i];
            int nx1 = now.x1 + dx[i];
            int ny2 = now.y2 + dy[i];
            int nx2 = now.x2 + dx[i];

            bool fallA = false;
            bool fallB = false;

            if (board[ny1][nx1] == false)fallA = true;
            if (board[ny2][nx2] == false) fallB = true;

            if (fallA == true && fallB == true) {
                continue;
            }
            if (fallA ^ fallB) {
                return now.count + 1;
            }

            if (board[ny1][nx1] == '#') {
                ny1 = ny1 - dy[i];
                nx1 -= dx[i];
            }
            if (board[ny2][nx2] == '#') {
                ny2 -= dy[i];
                nx2 -= dx[i];
            }

            if (!visited[ny1][nx1][ny2][nx2]) {
                q.push({ ny1,nx1,ny2,nx2,now.count + 1 });
                visited[ny1][nx1][ny2][nx2] = true;
            }
        }
    }
    return -1;
}

int main() {
    cin >> N >> M;
    pair<int, int> a, b;
    int cnt = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'o') {
                if (cnt == 0) a = { i, j };
                else b = { i, j };
                cnt++;
                board[i][j] = '.';
            }
        }
    }

    cout << BFS(a, b);
}