백준 16197 두 동전

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

16197번: 두 동전

 

#include<stdio.h>
#include<queue>
#include<algorithm> 
#include<iostream>
#define NSIZE 21
#define MSIZE 21
using namespace std;
char input[NSIZE][MSIZE];
int N, M;
int chk[NSIZE][MSIZE][NSIZE][MSIZE];
int dy[] = { 0,0,-1,1 };
int dx[] = { -1,1,0,0 };
struct Data {
    int y, x, y1, x1, cnt;
};
queue<Data>q;
void init() {
    int y, x, y1, x1;
    scanf("%d %d", &N, &M);
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> input[i][j];
            if (input[i][j] == 'o' && cnt == 0) {
                cnt++;
                y = i; x = j;
                input[i][j] = '.';
            }
            else if (input[i][j] == 'o' && cnt == 1) {
                y1 = i; x1 = j;
                input[i][j] = '.';
            }
        }
    }
 
    q.push({ y,x,y1,x1,0 });
    chk[y][x][y1][x1] = 1;
}
int Min = 0x7fffffff;
void bfs() {
 
    while (!q.empty()) {
        Data c = q.front(); q.pop();
        if (c.cnt > 10) {
            return;
        }
        int cnt = 0;
        if (c.y == 0 || c.y == N + 1 || c.x == 0 || c.x == M + 1) {
            cnt++;
        }
        if (c.y1 == 0 || c.y1 == N + 1 || c.x1 == 0 || c.x1 == M + 1) {
            cnt++;
        }
        if (cnt == 1) {
            if (Min > c.cnt) {
                Min = c.cnt;
            }
            return;
        }
        if (cnt == 2)continue;
        for (int dir = 0; dir < 4; dir++) {
            Data n = c;
            n.y += dy[dir];
            n.x += dx[dir];
            n.y1 += dy[dir];
            n.x1 += dx[dir];
            n.cnt++;
 
 
 
            if (input[n.y][n.x] != '#' && input[n.y1][n.x1] != '#') {//벽이면 원위치
                if (chk[n.y][n.x][n.y1][n.x1] == 0) {
                    chk[n.y][n.x][n.y1][n.x1] = 1;
                    q.push(n);
                }
            }
            //chk[n.y][n.x][n.y1][n.x1] == 0 &&
            if (input[n.y][n.x] == '#' && input[n.y1][n.x1] != '#') {//벽이면 원위치
                n.y = c.y; n.x = c.x;
                if (chk[n.y][n.x][n.y1][n.x1] == 0) {
                    chk[n.y][n.x][n.y1][n.x1] = 1;
                    q.push(n);
                }
            }
            if (input[n.y][n.x] != '#' && input[n.y1][n.x1] == '#') {//벽이면 원위치
                n.y1 = c.y1; n.x1 = c.x1;
                if (chk[n.y][n.x][n.y1][n.x1] == 0) {
                    chk[n.y][n.x][n.y1][n.x1] = 1;
                    q.push(n);
                }
            }
        }
    }
}
int main(void) {
 
    init();
    bfs();
    if (Min == 0x7fffffff)Min = -1;
    printf("%d", Min);
    return 0;
}

단순한 bfs이긴 한데 조금 조건이 들어간 탐색 문제 입니다 주의 할점은 동전이 이동하는 조건 인데
두동전이 한번에 움직이기 때문에
저는 세가지로 조건을 주었습니다
1번 동전과 2번 동전이 있다고 하면
두동전이 이동하는 위치에 벽이 아닌경우

1번 동전이 이동하는 위치에 벽이 있고
2번 동번이 이동하은 위치에 벽이 없고

그반대인 경우를 적어놓고 설계를 했고

0,0 부터 입력을 받게 되면 범위의 벗어난값이 -1가 되는게 있어 혹시나 해서 1,1부터 N, M 까지 받고
0,0이나 N+1, M+1 가되는 동전이 두개가 아니고 한개인경우에 값을 저장하고 리턴하는 식으로 구현했습니다

소스에 굳이 넣을필요없는 게 있긴하지만 참고 하고 봐주세요

오늘은 여기까지이고 즐거운 코딩 하세요

​