알고리즘 캠프에서 풀었던 다른 문제들:
알고리즘 캠프 인덱스
5일동안 풀었던 여러 유형의 백준 문제들 1일차 Brute Force 2일차 BFS 3일차 4일차 5일차 오전(A) A. 15650번 N과 M(2) B. 14501번 퇴사(+ 퇴사 2) 오후(B) A. 16922 로마숫자 만들기 B. 16917번 두 동전 C. 1693..
dongwook-chang.tistory.com
문제 링크:
16197번: 두 동전
N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다. 버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다. 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다. 동전이 이동하려는 방향에 칸이 없
www.acmicpc.net
자료구조를 잡는데 시간이 많이 걸렸는데, 선배님은 깔끔하게 x1, x2, y1, y2를 사용하셨다.
cost상한(10)이 주어져있기 때문에 trimming에 크게 신경쓰지 않아도 된다.
/* 1. cin.get() 사용법 */
/* 2. out = !IN 이어야 : !누락 */
/* 3. 할당을 못 받으면 모든 좌표가 초기화가 되지 않아 0이되버림, 기본적으로 pt를 할당해주어야 */
/* 4. emplace_back() 사용법 */
/* 5. 종료 조건 누락 : 문제 잘 읽기 ! */
/* 6. 인덱싱 잘하기! : 비용 10까지만 가능하면 9까지 자식 호출 허용해야! */
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M;
bool w[20][20];
vector<pair<int, int>> c;
bool v[20][20][20][20];
struct qnode {
pair<int, int> f, s;
int d;
};
int dn[] = { -1, 0, 1, 0 };
int dm[] = { 0, 1, 0, -1 };
#define IN(n, m) (0 <= (n) && (n) < N && 0 <= (m) && (m) < M)
int BFS() {
qnode rt;
rt.f = c[0], rt.s = c[1]; rt.d = 0;
v[rt.f.first][rt.f.second][rt.s.first][rt.s.second] = v[rt.s.first][rt.s.second][rt.f.first][rt.f.second] = 1;
queue<qnode> q; q.push(rt);
while (!q.empty()) {
qnode pt = q.front(); q.pop();
if (pt.d >= 10) /* 5 */ /* 6 */
return -1;
for (int d = 0; d < 4; ++d) {
// 순서 잘 정하기
int cff = pt.f.first + dn[d], cfs = pt.f.second + dm[d], csf = pt.s.first + dn[d], css = pt.s.second + dm[d];
// 나감 return
bool fout = !IN(cff, cfs), sout = !IN(csf, css); /* 2 */
if (fout || sout) {
if (fout && sout)
continue;
return pt.d + 1;
}
qnode cd = pt; /* 3 */
if (!w[cff][cfs]) cd.f = { cff, cfs };
if (!w[csf][css]) cd.s = { csf, css };
cd.d = pt.d + 1;
if (cd.f == cd.s) { // trimming
continue;
}
if (v[cd.f.first][cd.f.second][cd.s.first][cd.s.second]) {
continue;
}
v[cd.f.first][cd.f.second][cd.s.first][cd.s.second] = v[cd.s.first][cd.s.second][cd.f.first][cd.f.second] = 1;
q.push(cd);
}
}
return -1;
}
int main() {
cin >> N >> M; cin.get(); /* 1 */
for (int n = 0; n < N; ++n) {
for (int m = 0; m < M; ++m) {
switch (cin.get()) { /* 1 */
case '#': w[n][m] = 1; break;
case 'o': c.emplace_back(n, m); break;
}
}cin.get(); /* 1 */
}
cout << BFS();
return 0;
}