백준 16197 - 두 동전(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16197

16197번: 두 동전

그래프 탐색을 통해 푸는 문제입니다.

두 동전을 상하좌우 4방향으로 움직여 한 동전만 떨어뜨리는 문제입니다.

두 동전이 모두 떨어지는 상황만 나오거나, 10번보다 많이 움직이면 -1를 출력해주면 됩니다.

 

먼저 두 동전의 위치에서 시작합니다.

두 동전은 4방향 전부 움직일 수 있으니, 상하좌우를 모두 탐색해줘야합니다.

 

탐색을 할 때는 이동한 좌표를 통해 판별을 하는데,

1. 두 동전 모두 떨어진다. -> 해당 경우를 넘어간다.

2. 두 동전 중 하나만 떨어진다 -> 저장된 최소 값과 비교후, 다른 경우로 넘어간다.

3. 두 동전 중 어느 동전이 벽이 부딪힌다 -> 부딪힌 동전을 이전 좌표로 되돌린다.

4. 10번 넘게 움직이거나, 이번에 움직인 횟수가 최소 횟수보다 크다 -> 이번 경우는 넘어간다.

 

4가지의 경우를 확인한 뒤, 2번과 3번 조건만 다음 4방향 탐색을 해주면 됩니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N, M, ans = INF;
char map[21][21];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<P> coin;

bool move_out(int x, int y){
    if(x <= 0 || x > N || y <= 0 || y > M) return true;
    return false;
}

void bfs(int x1, int y1, int x2, int y2, int cnt, int dir){
    if(ans < cnt) return;
    if(cnt > 10) return;
    int xx1 = x1 + dx[dir];
    int yy1 = y1 + dy[dir];
    int xx2 = x2 + dx[dir];
    int yy2 = y2 + dy[dir];
    if(move_out(xx1, yy1) && move_out(xx2, yy2)) return;
    else if(move_out(xx1, yy1) && !move_out(xx2, yy2)) ans = min(ans, cnt);
    else if(!move_out(xx1, yy1) && move_out(xx2, yy2)) ans = min(ans, cnt);
    if(map[xx1][yy1] == '#'){
        xx1 = x1;
        yy1 = y1;
    }
    if(map[xx2][yy2] == '#'){
        xx2 = x2;
        yy2 = y2;
    }
    for(int i = 0; i < 4; i++){
        bfs(xx1, yy1, xx2, yy2, cnt + 1, i);
    }
}

void solve(){
   for(int i = 0; i < 4; i++){
       int x1 = coin[0].F;
       int y1 = coin[0].S;
       int x2 = coin[1].F;
       int y2 = coin[1].S;
       bfs(x1, y1, x2, y2, 1, i);
   }
   if(ans == INF) cout << "-1";
   else cout << ans;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
            if(map[i][j] == 'o'){ 
                coin.push_back({i, j});
            }
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요