https://www.acmicpc.net/problem/15684
2가지 방법을 사용해서 풀었습니다.
-
공통 사항
i가 i로 도착하는 지 확인하는건 같은 함수입니다.
잘 도착하는지 확인하는 함수는 엑셀처럼 가로선을 두껍게 생각하여,
a=1,b=1이면 (1,1)로 하고, a=2,b=4이면 (2,4)의 배열이 체크되도록 했습니다.
-
1. DFS
가로선의 갯수가 3으로 크지않은 수이기 때문에 완탐이 가능합니다.
따라서 DFS로 모두 완탐하고 시간절약에 유의하며 풀었습니다.
-
2. 가로선이 3개로 작은 것을 노려서 시간 단축
DFS의 단점은 가로선의 갯수가 1부터 시작하는 것이아닌
1->2->3->3->3….->3->2->3->3->…. 이런식으로 가게 됩니다.
따라서 가로선 1로 충분히 해결할 수 있을 경우 많은 시간이 소모됩니다.
따라서 저는 가로선이 3개인 것을 잡고, 가로선 1개일 때와 2개일때, 마지막으로 3개일때로 나눠서 풀었습니다.
가로선이 1일때 큐에 데이터를 집어넣고, 가로선이 2일때 큐에서 꺼내서 활용했으며, 가로선이 3일경우 DFS를 사용했습니다.
-
1. DFS
#include <iostream> #include <queue> using namespace std; int n, m, h, a, b; int result = 2e9; bool ch[32][11]; bool check() {//i가 i로 가는지 Check~ for (int i = 1; i <= n; i++) { int num = i;//세로선 number for (int j = 1; j <= h; j++) {//내려오다가 if (ch[j][num] == true) num += 1; //선을 만나면 한칸 >>로 else if (ch[j][num - 1] == true) num -= 1;//왼쪽칸의 선을 만나면 <<로 if (j == h) {//다 내려왔는데 같은 num이 아니면 false로 끝 if (num != i) return false; } } } return true; } void dfs(int row, int col, int cnt) { if (cnt >= result || cnt > 3) return; else if (check()) { result = result < cnt ? result : cnt; return; } for (int i = row; i <= h; i++, col = 1) { for (int j = col; j < n; j++) {//★i=1,j=1이아닌 과거 위치에서 시작!!! 처음부터 돌리는게 아니다!! if (ch[i][j] == false && ch[i][j + 1] == false && ch[i][j - 1] == false) { ch[i][j] = true; dfs(i, j + 2, cnt + 1); ch[i][j] = false; } } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> h; for (int i = 1; i <= m; i++) { cin >> a >> b; ch[a][b] = true; } if (check()) {//선 아무것도 추가하지 않았을 때 cout << "0\n"; return 0; } dfs(1, 1, 0); if (result == 2e9) cout << "-1\n"; else cout << result << '\n'; }
-
2. 가로선이 3개로 작은 것을 노려서 시간 단축
#include <iostream>
#include <queue>
using namespace std;
//10:35
int n, m, h, a, b;
bool ch[31][11];
bool ok;//ok를 줘서 dfs에서 더이상 연산하지 못하도록
queue <pair<int, int>> q;
bool check() {//i가 i로 가는지 Check~
for (int i = 1; i <= n; i++) {
int num = i;//세로선 number
for (int j = 1; j <= h; j++) {//내려오다가
if (ch[j][num] == true) num += 1; //선을 만나면 한칸 >>로
else if (ch[j][num - 1] == true) num -= 1;//왼쪽칸의 선을 만나면 <<로
if (j == h) {//다 내려왔는데 같은 num이 아니면 false로 끝
if (num != i) return false;
}
}
}
return true;
}
void dfs(int row, int col, int cnt) {
if (ok == true) return;
if (cnt == 3) {//가로선 1,2일때는 앞에서 했으므로 3일때만 체크
if (check()) {
cout << "3\n";
ok = true;//이제 더이상 연산은 무의미 함.
}
return;
}
for (int i = row; i <= h; i++,col=1) {
for (int j = col; j < n; j++) {//★i=1,j=1이아닌 과거 위치에서 시작!!! 처음부터 돌리는게 아니다!!
if (ch[i][j] == false && ch[i][j + 1] == false && ch[i][j - 1] == false) {
ch[i][j] = true;
dfs(i,j+2,cnt + 1);
if (ok == true)return;
ch[i][j] = false;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> h;
for (int i = 1; i <= m; i++) {
cin >> a >> b;
ch[a][b] = true;
}
if (check()) {//가로선을 추가하지 않았을 때
cout << "0\n";
return 0;
}
for (int i = 1; i <= h; i++) {//가로선을 하나만 추가했을 때
for (int j = 1; j < n; j++) {
if (ch[i][j] == false && ch[i][j + 1] == false && ch[i][j - 1] == false) {
ch[i][j] = true;
q.push(make_pair(i, j));
if (check()) {
cout << "1\n";
return 0;
}
ch[i][j] = false;
}
}
}
while (!q.empty()) {//가로선을 두개만 추가했을 때
int x = q.front().first;
int y = q.front().second;
q.pop();
ch[x][y] = true;
for (int i = 1; i <= h; i++) {
for (int j = 1; j < n; j++) {
if (ch[i][j] == false && ch[i][j + 1] == false && ch[i][j - 1] == false) {
ch[i][j] = true;
if (check()) {
cout << "2\n";
return 0;
}
ch[i][j] = false;
}
}
}
ch[x][y] = false;
}
dfs(1,1,0);//가로선 세개는 dfs로
if (ok == false) cout << "-1\n";
}
- 혼잣말
-
dfs안에서 반복문 돌릴때 처음부터 돌리지말고 해당위치를 파라미터로 넘겨서 해당위치부터 돌려야 시간이 엄청나게 단축된다. 이걸 생각 못해서 많은 시간을 버렸다…..ㅠㅠ
-
boj에서 런타임에러나면 배열크기를 잘줬는지 확인하자..