(출처) https://www.acmicpc.net/problem/17070
완전탐색
해당 문제는 파이프를 특정 위치까지 옮기는 방법의 수를 구하는 문제이다.
즉 경우의 수를 구하는 문제라고 볼 수 있다.
처음 입력 조건을 보았을 때 입력으로 주어지는 맵의 크기 변수 N의 최대치가 16 정도 밖에 안되길래 완전탐색으로 충분히 풀 수 있을 것 같은 예감이 들었다.
문제에서 파이프가 움직이는 경우는 아래로 한 칸, 혹은 오른쪽으로 한 칸, 혹은 아래와 오른쪽 각각 한 칸 이 3가지 패턴 중 하나가 되기 때문에 파이프가 360도 회전하여 제자리로 되돌아 오는 식의 움직임은 존재할 수 없었다.
즉 제자리로 되돌아오는 사이클이 존재하지 않기 때문에 파이프를 옮기는 방법에 대한 경우의 수는 닫힌 상태로 정해져 있다.
따라서 해당 문제에서 파이프를 옮길 수 있는 방법의 총 경우의 수를 한번 대략적으로 계산해 보았는데, 현재 파이프의 위치 상태에 따라서 이동할 수 있는 방법의 수가 3가지에서 2가지로 계속 달라지고, 파이프가 이동하는 횟수도 정확하게 추측하기는 복잡한 관계로 대략적으로만 계산을 해 보기로 했다.
파이프는 반드시 3가지 유형으로 목적지를 향해 최소 1칸(하 or 우로 이동), 최대 2칸(대각으로 이동) 움직이게 되므로 맵의 끝까지 파이프가 이동하는 평균 이동 횟수를 얼추 N 번으로 수렴한다고 가정하고, 매 이동 시 선택할 수 있는 파이프의 방향(경우의 수가 갈리는 분기점)도 평균적으로는 2.5개 정도 되지만 그냥 넉넉잡아 3으로 계산하게 된다면, 전체 경우의 수는 3^N 개가 된다.
이때 입력으로 들어올 수 있는 N의 최댓값은 16이므로 넉넉잡아 계산했어도 결국 5천만 개 미만의 경우의 수를 탐색하는 것이 되므로 완전탐색으로도 충분히 주어진 시간제한 1초에 문제를 해결할 수 있을 것 같았다.
따라서 DP를 이용한다던가 추가적인 최적화는 신경 쓰지 않고 우선은 완전탐색으로 방향을 잡았다.
DFS로 구현
DFS를 이용한 완전탐색 방식으로 코드를 짜기로 했다.
문제에서 파이프는 총 2칸을 차지하는 크기를 갖는데 모든 움직임을 파이프의 오른쪽 기준으로 바라보기로 했다. (파이프의 위치상태가 세로라면 아래쪽 기준)
파이프를 어떤 방법으로 이동하든 간에 어차피 파이프의 왼쪽 부분은 파이프의 오른쪽 부분이 이전에 차지하고 있었던 자리를 뒤따라갈 뿐이므로, 왼쪽 부분이 벽에 걸리거나 막히는 상황은 고려하지 않아도 될 것이라고 판단했다.
따라서 파이프의 오른쪽 자리 좌표를 기준으로 문제에서 정해진 규칙에 따라서 이동시켰을 때, 맵의 (N - 1, N -1) 좌표로 도달하는 모든 경우의 수를 카운트 하였고, (N-1,N-1) 좌표까지의 이동과정은 특별할 것 없이 재귀를 이용한 DFS로 구현하였다.
코드
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
//파이프의 오른쪽이 기준점(세로 방향의 경우 밑쪽이 기준)
struct Pipe{
int row, col, state;
};
int cd0[2][2] = {{0,1}, {1,1}}; //가로
int cd1[2][2] = {{1,0}, {1,1}}; //세로
int cd2[3][2] = {{0,1}, {1,0}, {1,1}}; //대각선
vector<int (*)[2]> cd = {cd0, cd1, cd2}; // cd 배열들을 묶는 포인터 배열
vector<vector<int>> map;
int visited[16][16];
int N;
int result;
void solution(Pipe pipe) {
//목표지점에 도착한 경우
if (pipe.row == N - 1 && pipe.col == N - 1) {
result++;
return;
}
visited[pipe.row][pipe.col] = 1;
int remaining_nm;
if (pipe.state == 2) remaining_nm = 3;
else remaining_nm = 2;
for (int i = 0; i < remaining_nm; i++) {
//이동 후 state 상태 계산
int next_state;
if (cd[pipe.state][i][0] == 0 && cd[pipe.state][i][1] == 1) next_state = 0;
else if(cd[pipe.state][i][0] == 1 && cd[pipe.state][i][1] == 0) next_state = 1;
else next_state = 2;
//이동로직
int dy, dx;
dy = pipe.row + cd[pipe.state][i][0];
dx = pipe.col + cd[pipe.state][i][1];
if (visited[dy][dx]) continue;
if (dy < 0 || dx < 0 || dy >= N || dx >= N) continue;
if (map[dy][dx]) continue;
if (next_state == 2 && (map[dy-1][dx] || map[dy][dx-1])) continue;
Pipe next_pipe = {dy, dx, next_state};
solution(next_pipe);
visited[dy][dx] = 0;
}
return ;
}
int main() {
//인풋 입력
cin >> N;
if (N <= 2) {
cout << "0" << "\n";
return 0;
}
map = vector<vector<int>> (N, vector<int>(N,-1));
for(int y = 0; y < N; y++){
for (int x = 0; x < N; x++){
int temp;
cin >> temp;
map[y][x] = temp;
}
}
//최초 초기화 과정
memset(visited, 0, sizeof(visited));
visited[0][0] = 1;
result = 0;
Pipe start = {0,1,0};
//본 로직
solution(start);
//아웃풋 출력
cout << result << "\n";
return 0;
}
기억하고 싶은 점
처음 DFS를 구현하고자 할 때 여태껏 재귀로만 구현했지 Stack으로는 한 번도 구현해보지 않았기 때문에 Stack을 한 번 이용해보려고 했다.
그런데 막상 Stack으로 DFS를 구현하니 한 가지 문제가 생기더라.
바로 특정 지점을 방문하고 나서 실패하거나 성공하여 다시 되돌아오는 과정을 구현하기 위해서는 방문했다고 체크한 Visited 배열을 다시 방문하지 않은 상태로 되돌려놓는 과정이 필요한데 Stack으로 DFS를 구현하면 그것을 구현하는 것이 어렵다는 것이다.
따라서 결국 다시 재귀로 코드를 짜는 것으로 방향을 바꿨다.
경우의 수를 카운팅한다든지 이런 완전탐색에서 DFS를 이용할려면 재귀를 사용하는 것이 맞는 것 같다.
