Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
Tags
- 유니온 파인드
- 문자열
- 에라토스테네스의 체
- 구현
- JUnit 5
- swea
- dfs
- 세그먼트 트리
- 스택
- mst
- 백준
- java
- 위상정렬
- Kotlin
- 동적계획법
- Effective Java
- 시뮬레이션
- 백트래킹
- 완전탐색
- 프로그래머스
- BFS
- 알고리즘
- 그리디
- 투 포인터
- 후니의 쉽게 쓴 시스코 네트워킹
- Network
- 플로이드-와샬
- CS
- 이분탐색
- 수학
Archives
반갑습니다!
[백준] 16197 두 동전 본문
풀이
시뮬레이션 문제이다. BFS를 통해 모든 경우를 탐색하여 해결하였다. 이 때, 동전이 2개이므로 중복 체크를 위한 배열을 visited[cy1][cx1][cy2][cx2]
로 두었다.
코드
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct Coins {
int x1, y1, x2, y2, cnt;
};
int n, m, cx1, cy1, cx2, cy2;
char map[20][20];
bool visited[20][20][20][20];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
bool inRange(int x, int y) {
return (0 <= x && x < m) && (0 <= y && y < n);
}
int bfs() {
queue<Coins> q;
q.push({ cx1, cy1, cx2, cy2, 0 });
visited[cy1][cx1][cy2][cx2] = true;
while (!q.empty()) {
Coins cur = q.front();
q.pop();
// 버튼을 10번보다 많이 누르면 종료
if (cur.cnt > 10) break;
for (int i = 0; i < 4; i++) {
int nx1 = cur.x1 + dx[i]; int ny1 = cur.y1 + dy[i];
int nx2 = cur.x2 + dx[i]; int ny2 = cur.y2 + dy[i];
// 한 동전만 보드를 벗어난 경우
if ((inRange(nx1, ny1) && !inRange(nx2, ny2)) || (!inRange(nx1, ny1) && inRange(nx2, ny2))) {
if (cur.cnt + 1 > 10) return -1;
return cur.cnt + 1;
}
// 두 동전 다 보드를 벗어난 경우
if (!inRange(nx1, ny1) && !inRange(nx2, ny2)) continue;
// 동전1이 벽을 만난 경우 원래 위치로 복귀
if (map[ny1][nx1] == '#') {
nx1 -= dx[i]; ny1 -= dy[i];
}
// 동전2가 벽을 만난 경우 원래 위치로 복귀
if (map[ny2][nx2] == '#') {
nx2 -= dx[i]; ny2 -= dy[i];
}
if (!visited[ny1][nx1][ny2][nx2]) {
q.push({ nx1, ny1, nx2, ny2, cur.cnt + 1 });
visited[ny1][nx1][ny2][nx2] = true;
}
}
}
return -1;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
bool first = true;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> map[i][j];
if (map[i][j] == 'o') {
if (first) {
cx1 = j; cy1 = i;
first = false;
}
else {
cx2 = j; cy2 = i;
}
}
}
cout << bfs() << '\n';
return 0;
}
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 3987 보이저 1호 (0) | 2020.04.30 |
---|---|
[백준] 9655 돌 게임 (0) | 2020.04.29 |
[백준] 14500 테트로미노 (0) | 2020.04.29 |
[백준] 14499 주사위 굴리기 (0) | 2020.04.29 |
[프로그래머스] 튜플 (0) | 2020.04.29 |