문제 이해 단계
https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
NxN짜리 격자판이 존재한다. 그리고 중간에 벽(1)이 존재한다.
그리고 2칸을 차지하는 파이프가 존재하는데, 무조건 (1,1)과 (1,2)에서 시작한다.
목표는 파이프가 벽에 부딪히지 않고, (N, N)까지 이동하는 것이다.
파이프는 회전이 가능한데, 움직이면서 회전이 가능하다.
회전은 한 번에 45도씩만 가능하다.
움직이는 방향은 →↓↘으로만 움직일 수 있다.
움직이는 방향과 회전시킬 수 있는 선택지는 그림으로 잘 나와있다.
위 그림을 참고하면 편하다.
색이 입혀진 칸은 파이프가 해당 칸을 차지한다는 뜻이다.
즉 해당 칸에 벽이 있으면 안 된다는 것이다.
해당 조건일 때, (N, N)까지 갈 수 있는 경우의 수를 구하는 문제
문제 접근 단계
일단 문제 조건부터 살펴본다.
맵의 크기 N이 최대 16x16이다.
엄청나게 작기 때문에 완전 탐색이 가능하다.
그래서 다양한 방식으로 문제에 접근할 수 있을 것 같다.
내가 생각하기에 해당 문제의 핵심은, 현재 파이프의 방향을 인식하는 것이다.
왜냐하면 현재 파이프의 상태에 따라 움직일 수 있는 방향이 달라지기 때문이다.
그래서 현재 파이프의 상태를 인식하는 것부터 시작한다.
파이프의 현재 상태 인식
파이프는 무조건 2칸짜리 직사각형으로 이뤄져 있다.
그래서 나는 이를 머리칸과 꼬리칸 두 개의 좌표를 따로 받아서 현재 상태를 판단하기로 했다.
만약 머리칸과 꼬리칸의 x좌표가 동일하다면 세로로 서있는 상태,
y좌표가 동일하다면 가로로 누워있는 상태,
둘 다 아니라면 대각선으로 있는 상태로 볼 수 있다.
방향을 정했으면, 방향마다 정해진 움직임을 따로 만들어서 그것대로 움직여주면 된다.
이 점을 제외하고는 일반적은 그래프 탐색 문제와 같다.
나는 DFS로 하는 것이 더 안전할 것 같아서 DFS로 풀었다.
BFS로도 풀릴 것 같긴 하다.
참고로 한쪽 방향으로만 움직이고 돌아가진 않기 때문에
방문 확인은 딱히 필요 없을 것 같다.
이제 문제 구현 단계를 가서 문제를 풀어보자.
문제 구현 단계
#include <iostream>
#include <vector>
using namespace std;
struct Point{
int x;
int y;
};
int N;
int ans = 0;
int map[17][17] = {0,};
// 2 버전의 방향을 생각
// 0번 -> 가로로 움직일 때(x축이 같을 때)
// 1번 -> 세로로 움직일 때(y축이 같을 때)
// 대각선 움직임은 두 움직임을 합친 것이기 때문에 따로 안만들어줌
int dx[2][2] = {{1,0},{1,1}};
int dy[2][2] = {{1,1},{1,0}};
// 머리칸, 꼬리칸의 좌표를 받음
void dfs(Point head, Point tail){
int x1 = head.x;
int y1 = head.y;
int x2 = tail.x;
int y2 = tail.y;
// 머리칸이 (N,M)에 도달하면 종료
if(x1 == N && y1 == N) {
ans++;
return;
}
bool diag = false; // 대각선인지 체크
int idx = 0; // 가로 세로 체크
if(x1 == x2) idx = 0; // 가로 일때
else if(y1 == y2) idx = 1; // 세로 일 때
else diag = true; // 대각선 일 때
for(int i = 0; i < 2; i++){
int nx = x1 + dx[idx][i];
int ny = y1 + dy[idx][i];
if(i == 0){
// 대각선으로 움직이는 경우
// 움직이는 범위 위와 왼쪽도 체크
if(map[nx-1][ny] == 1 || map[nx][ny-1] == 1) continue;
}
if(nx > N || ny > N || map[nx][ny] == 1) continue;
dfs({nx,ny},head); // 움직인 쪽을 머리로, head를 꼬리로 변경해 재귀호출
}
// 대각일 경우
if(diag){
// 가로인 움직임에 세로인 움직임을 한번 더 해서 판단
int nx = x1 + dx[1][1];
int ny = y1 + dy[1][1];
if(!(nx > N || ny > N || map[nx][ny] == 1)) dfs({nx,ny},head);
}
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> N;
for(int i = 1; i<= N; i++)
for(int j = 1; j <= N; j++) cin >> map[i][j];
dfs({1,2},{1,1});
cout << ans;
}전체 코드이다.
일단 전역변수 부분부터 보면 움직이는 방향을 설정해 줄 때,
따로 대각 방향은 설정해주지 않았다.
그 이유는 어차피 대각 방향은 가로, 세로 방향의 움직임을 합한 것이기 때문이다.
핵심으로 봐야 할 것은 dfs함수 부분인데,
매개변수로 현재 head와 tail의 위치가 들어간다.
head와 tail의 위치를 판단하여 현재 파이프가 어떤 상태인지 판단한 후 상응하는 움직임을 한다.
그리고 위치를 이동시켜 준 후, 그 위치로 하는 dfs를 한번 더 호출한다.
그렇게 계속 dfs를 호출하다가, head의 위치가 (N, N)에 오면 경우의 수+1을 해준다.
전체적인 설명은 여기까지이다. 설명을 마치겠다.
시행착오
태그를 보니까 DP로도 풀 수 있긴 하던데, 한번 보긴 해야겠다.
난 이걸 DP로 푼다는 게 상상이 안된다.
아무리 봐도 그래프 탐색으로 밖에 못 풀겠는데,
1시간 안에 푸는 것은 실패했다. 정확히는 1시간 30분 걸렸다.
나한테 이 문제는 dfs문제라기 보단 구현 문제에 가까웠던 것 같다.
한마디로 그냥 구현하기가 힘들었다.
생활비..