그림으로 설명해보자면 다음과 같다
map[a][5]
= 5,6번 세로선이 a번째 점선으로 연결된다는 의미이기 때문이다map[a][b]
가 연결되었다면 가로선이 서로 연결될 수 없다는 문제 조건 때문에 map[a][b-1], map[a][b+1]
은 연결 될 수 없다👩💻1. dfs 함수
(1,1)
부터(H,N-1)
까지 차례대로 연결선을 추가해보며 사다리 조건에 맞는지 탐색한다
void dfs(int cnt, int y, int x)
①cnt
: 현재 몇 개의 연결선을 추가했는지이고,
문제에서 최대 3개까지 추가할 수 있다고 했으므로 3개가 되기 전까지는 계속 사다리 조건에 맞는지 탐색한다
②(y,x)
: 연결선을 추가할 시작점. 매번dfs
를 다시 호출할 때마다x
는1
늘려준다
map[a][b]
에 연결선을 추가하려면map[a][b],map[a][b-1],map[a][b+1]
에 다 연결선이 없는지 확인해야 한다
- 연결선을 그어주고 모든 탐색을 마치고 왔을 때는 다시 연결선을 없애주어
(map[a][b]=0)
다른 곳에 연결선을 그었을 때를 탐색해준다void dfs(int cnt, int y, int x) { if (cnt >= minCnt) return; if (check()) { minCnt = cnt; return; } if (cnt == 3) return; for (int i = y; i <= H; i++) { for (int j = x; j < N; j++) { if (map[i][j] != 1 && map[i][j - 1] != 1 && map[i][j + 1] != 1) { map[i][j] = 1; dfs(cnt + 1, y, x+1); map[i][j] = 0; } } } }
👩💻2. i번 세로선의 결과가 i번인지 check
- 각 세로선마다 한 단계씩 내려가면서 가로선이 그어진 게 있는지 확인해야 한다.
- 현재 위치에서 그어진 것이 있다면 오른쪽으로 이동했다는 뜻이니까 현재 위치
pos++
해준다- 현재 위치 앞에서 그어진 것이 있다면 다시 왼쪽으로 이동한다는 뜻이니
pos--
해준다- 마지막 위치
pos
가i
번에 있는지 확인bool check() { for (int i = 1; i <= N; i++) { int pos = i; for (int j = 1; j <= H; j++) { if (map[j][pos] == 1) pos++; else if (map[j][pos - 1] == 1) pos--; } if (pos != i) return false; } return true; }
전체코드
#include <iostream> #include <vector> using namespace std; int minCnt=4; int N, M, H; vector<vector<int>> map; bool check() { for (int i = 1; i <= N; i++) { int pos = i; for (int j = 1; j <= H; j++) { if (map[j][pos] == 1) pos++; else if (map[j][pos - 1] == 1) pos--; } if (pos != i) return false; } return true; } void dfs(int cnt, int y, int x) { if (cnt >= minCnt) return; if (check()) { minCnt = cnt; return; } if (cnt == 3) return; for (int i = y; i <= H; i++) { for (int j = x; j < N; j++) { if (map[i][j] != 1 && map[i][j - 1] != 1 && map[i][j + 1] != 1) { map[i][j] = 1; dfs(cnt + 1, y, x+1); map[i][j] = 0; } } } } void init() { cin >> N >> M >> H; map = vector<vector<int>>(H + 1, vector<int>(N + 1, 0)); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; map[a][b] = 1; } } int main() { init(); dfs(0, 1,1); if (minCnt == 4) cout << "-1" << endl; else cout << minCnt << endl; return 0; }