[BOJ/백준] 16197 두 동전

● [문제번호 16197] 두 동전

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

16197번: 두 동전

 

 

● 알아야 할 것

: BFS

: 구조체 (struct)

 

 

● 풀이 과정

: 처음에 Queue를 2개 써서 풀어보려고 시도를 해보았다.

하지만 다음 회차에 이동할 자리가 {동전1 : 벽 / 동전2 : 빈 칸}인 경우 처리하기가 어려워지고 지저분해져서 고민을 했다.

 

: 구글링을 통해 알아낸 아이디어는 Queue의 자료형을 pair 2개로 하는 것이었다.

그래서 잘 구현되다가 이번에는 동전의 이동횟수를 세는 문제점을 마주했다.

 

: 좀 더 고민을 하여 생각해낸 아이디어는 Queue의 자료형을 구조체, Class로 만드는 것이었다.

다행이도 여차여차 구현되어 통과를 하였다.

 

문제에서 생각해야하는 것은

두 동전을 동시에 움직여야하는 것이다.

따라서 두 동전의 위치를 함께 저장해야한다.

그리고 그 위치까지 오는데 사용된 이동횟수도 알아야한다.

 

BFS를 이용하여 최단거리를 응용한 형태로 구현되었다.

 

현재 위치에서 다음 위치로 갈 두 동전에 대하여

1. 두 동전 모두 보드 밖으로 떨어진다.

→ PASS

 

2. 두 동전 모두 보드 안에 있다.

2-1. 각 동전이 벽을 만난다면

→ 그 동전의 다음 이동좌표는 이동하지않고 동일하다.

2-2. 각 동전이 벽을 안 만났다면

→ 다음 이동좌표로 이동한다.

(두 동전이 모두 벽을 만난 경우는 방문기록에 의해 막힌다.)

(따라서 1개의 동전만 벽을 만난 경우는 방문기록에 의해 분기될 수 있다.)

 

3. 1개의 동전만 보드 밖으로 떨어진다.

→ 정답 반환

 

 

● 주의 할 것

: index를 주의하여 작성하고, 각 분기의 내용을 잘 이해해야한다.

 

 

● 참고 할 것

: NULL

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 각 케이스에서 두 동전의 위치와 방향 이동횟수를 묶음으로 저장
struct coin
{
    int x1, y1, x2, y2;
    int cnt;
};

// controlX : 보드 위에서 이동하기 위한 상, 하, 좌, 우
// controlY : 보드 위에서 이동하기 위한 상, 하, 좌, 우
// visited[동전1 X좌표][동전1 Y좌표][동전2 X좌표][동전2 Y좌표] : 두 동전의 방문기록
// board : 보드게임 상태 저장
// start : 두 동전의 시작위치 저장
int controlX[4] = {-1, 1, 0, 0};
int controlY[4] = {0, 0, -1, 1};
bool visited[21][21][21][21];
char board[21][21];
vector<pair<int, int>> start;
int N, M;

// 보드 밖으로 나갔는 지 확인 함수
bool outRange(int x, int y)
{
    if(x < 1 || N < x)
        return true;
    else if(y < 1 || M < y)
        return true;
    else
        return false;
}

int bfs()
{
    queue<coin> q;
    
    // 두 동전의 시작점 저장
    q.push({start[0].first, start[0].second, start[1].first, start[1].second, 0});
    
    while(!q.empty())
    {
        coin c = q.front();
        
        int fromX1 = c.x1;
        int fromY1 = c.y1;
        
        int fromX2 = c.x2;
        int fromY2 = c.y2;
        
        int from = c.cnt;
        
        // 방문 체크인
        visited[fromX1][fromY2][fromX2][fromY2] = true;
        
        q.pop();
        
        // 상, 하, 좌, 우
        for(int i = 0; i < 4; i++)
        {
            int toX1 = fromX1 + controlX[i];
            int toY1 = fromY1 + controlY[i];
            
            int toX2 = fromX2 + controlX[i];
            int toY2 = fromY2 + controlY[i];
            
            int to = from + 1;
            
            // 이동횟수가 10번 이상인 경우
            if(11 < to)
                return -1;
            
            // 다음 이동 좌표가 보드 밖인지 확인
            bool X1Y1 = outRange(toX1, toY1);
            bool X2Y2 = outRange(toX2, toY2);
            
            // 두 동전 모두 보드 밖인 경우
            if(X1Y1 && X2Y2)
                continue;
            // 두 동전 모두 보드 안인 경우
            else if(!X1Y1 && !X2Y2)
            {
                // 동전1이 벽을 만나게 된 경우
                if(board[toX1][toY1] == '#')
                {
                    toX1 = fromX1;
                    toY1 = fromY1;
                }
                // 동전2가 벽을 만나게 된 경우
                if(board[toX2][toY2] == '#')
                {
                    toX2 = fromX2;
                    toY2 = fromY2;
                }
                // 방문하지 않은 경우 queue에 저장
                if(!visited[toX1][toY1][toX2][toY2])
                    q.push({toX1, toY1, toX2, toY2, to});
            }
            // 두 동전 중 1개만 떨어진 경우
            else
                return to;
        }
    }
    
    // 두 동전 모두 떨어뜨릴 수 없는 경우
    return -1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // 보드게임 상태 저장
    for(int n = 1; n <= N; n++)
    {
        for(int m = 1; m <= M; m++)
        {
            cin >> board[n][m];
            
            // 동전의 시작 위치 저장
            if(board[n][m] == 'o')
                start.push_back(pair<int, int>(n, m));
        }
    }
    
    int sol = bfs();
    
    // 버튼을 10번 보다 많이 눌러야한다면
    if(10 < sol)
        cout << -1;
    // 버튼을 10번 이하 눌러야한다면
    else
        cout << sol;
        
    return 0;
}

 

 

● [백준] - [알고리즘 중급 1/3] - [531 - 브루트 포스 - 재귀 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	6603	로또	https://pirateturtle.tistory.com/301
2	1182	부분수열의 합	https://pirateturtle.tistory.com/302
3	14225	부분수열의 합	https://pirateturtle.tistory.com/303
4	14888	연산자 끼워넣기	https://pirateturtle.tistory.com/304
5	15658	연산자 끼워넣기 (2)	https://pirateturtle.tistory.com/305
6	14500	테트로미노	https://pirateturtle.tistory.com/306
7	16197	두 동전	https://pirateturtle.tistory.com/307
8	16198	에너지 모으기	https://pirateturtle.tistory.com/308
9	9663	N-Queen	https://pirateturtle.tistory.com/309
10	2580	스도쿠	https://pirateturtle.tistory.com/310
11	4574	스도미노쿠	https://pirateturtle.tistory.com/311
12	1987	알파벳	https://pirateturtle.tistory.com/312