이번에는 백준 17070번 파이프 옮기기 1 문제를 풀어보았습니다.
처음에는 DFS만으로도 구현할 수 있었지만, 같은 위치와 같은 방향을 여러 번 방문하게 되어 중복 계산이 많이 발생했습니다.
현재 파이프의 끝 위치와 방향이 같다면 이후 이동 가능한 경우의 수는 항상 같기 때문에, 메모이제이션을 추가한 DP(Top-Down) 방식으로 해결하였습니다.
문제 설명
파이프의 한쪽 끝은 처음에 (1,2)에 있으며 방향은 가로입니다.
파이프를
- 오른쪽
- 아래
- 오른쪽 아래(대각선)
방향으로 이동시켜
끝점을 (N,N)으로 이동시키는 방법의 수를 구하는 문제입니다.
풀이 아이디어
현재 상태를
- 파이프 끝의 좌표
- 현재 파이프의 방향
으로 정의하였습니다.
같은 위치와 같은 방향이라면 이후에 이동 가능한 경우의 수는 항상 같으므로 DP를 사용할 수 있습니다.
DFS를 수행하면서 이미 계산한 상태는 그대로 재사용하도록 구현하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
int arr[16][16];
int dp[16][16][3];
vector<pair<int,int>> dirs = {
{0,1},
{1,0},
{1,1}
};
int dfs(int y,int x,int direction){
if(y==N-1 && x==N-1)
return 1;
int &ret = dp[y][x][direction];
if(ret!=-1)
return ret;
int cnt=0;
for(int i=0;i<3;i++){
int ny=y+dirs[i].first;
int nx=x+dirs[i].second;
if(ny>=N || nx>=N)
continue;
if(dirs[i].first==1 && dirs[i].second==1){
if(arr[ny][x] || arr[y][nx] || arr[ny][nx])
continue;
}else{
if(arr[ny][nx])
continue;
if(direction==0 && dirs[i].first==1 && dirs[i].second==0)
continue;
if(direction==1 && dirs[i].first==0 && dirs[i].second==1)
continue;
}
cnt += dfs(ny,nx,i);
}
return ret = cnt;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cin >> arr[i][j];
}
}
memset(dp,-1,sizeof(dp));
cout << dfs(0,1,0);
return 0;
}풀이 흐름
- 현재 파이프의 끝 좌표와 방향을 상태로 정의합니다.
- 현재 방향에서 이동 가능한 방향만 확인합니다.
- 이동 가능한 위치인지 검사합니다.
- 가능한 모든 방향으로 DFS를 수행합니다.
- 같은 상태는 DP를 이용하여 재사용합니다.
(N-1, N-1)에 도착하면 1을 반환하여 경우의 수를 계산합니다.
구현 포인트
1. DP 상태 정의
DP는
dp[y][x][direction]형태로 사용하였습니다.
의미는
현재 파이프의 끝이 (y,x)에 있고 방향이 direction일 때 목적지까지 이동하는 경우의 수입니다.
2. 방향에 따른 이동
파이프의 방향에 따라 이동 가능한 방향이 달라집니다.
가로인 경우
- 오른쪽
- 대각선
세로인 경우
- 아래
- 대각선
대각선인 경우
- 오른쪽
- 아래
- 대각선
으로 이동할 수 있도록 처리하였습니다.
if(direction==0 && ...)
continue;
if(direction==1 && ...)
continue;3. 대각선 이동 조건
대각선으로 이동하기 위해서는
세 칸이 모두 비어 있어야 합니다.
if(arr[ny][x] ||
arr[y][nx] ||
arr[ny][nx])
continue;하나라도 벽이 존재하면 이동할 수 없습니다.
4. 메모이제이션
이미 계산한 상태는 다시 계산하지 않습니다.
int &ret = dp[y][x][direction];
if(ret != -1)
return ret;같은 위치와 같은 방향에서는 이후 가능한 이동 경우의 수가 항상 같으므로 DP를 사용할 수 있습니다.
5. 종료 조건
파이프의 끝이 목적지에 도착하면
하나의 경로를 완성한 것이므로
return 1;을 반환합니다.
각 DFS는 자신의 모든 자식의 반환값을 더하면서
최종적으로 전체 경우의 수를 계산합니다.
6. V1과 V2의 차이
V1은 단순 DFS로 구현하였습니다.
같은 상태를 여러 번 방문하기 때문에 중복 계산이 매우 많이 발생합니다.
V2에서는
dp[y][x][direction]을 추가하여 메모이제이션을 적용하였습니다.
이미 계산한 상태는 그대로 반환하므로 중복 탐색이 제거되어 훨씬 빠르게 문제를 해결할 수 있었습니다.
