백준 17070번 파이프 옮기기 1

 

 

문제 보러가기 : https://www.acmicpc.net/problem/17070

 

 

 

17070번: 파이프 옮기기 1

 

 

이번 문제는 그래프 탐색 문제였습니다.

 

DFS / BFS 둘 다 문제 풀이 하겠습니다.

파이프의 한쪽 끝을 (n, n) 으로 이동시키는 방법의 개수를 출력해야하기 때문에 방문 여부를 확인해줄 필요는 없습니다.

 

 

 

 

BFS 설명

 

《문제 풀이》

 

1. 집의 상태를 배열로 입력 받고 파이프 옮기기

2. 파이프가 가로 / 세로 / 대각선 방향 중 어느 방향의 파이프인지 알기 위해 해당 좌표와 함께 큐에 삽입 

   --> queue<pair<pair<int, int>, int>> q

3. 현재 파이프가 가로 방향의 파이프이면

     (1) 가로 파이프로 놓을 수 있는지 확인하고 놓을 수 있으면 큐에 삽입

     (2) 대각선 파이프로 놓을 수 있는지 확인하고 놓을 수 있으면 큐에 삽입 

4. 현재 파이프가 세로 방향의 파이프이면

     (1) 세로 파이프로 놓을 수 있는지 확인하고 놓을 수 있으면 큐에 삽입

     (2) 대각선 파이프로 놓을 수 있는지 확인하고 놓을 수 있으면 큐에 삽입

5. 현재 파이프가 대각선 방향의 파이프이면

     (1) 가로 파이프로 놓을 수 있는지 확인하고 놓을 수 있으면 큐에 삽입

     (2) 세로 파이프로 놓을 수 있는지 확인하고 놓을 수 있으면 큐에 삽입

     (3) 대각선 파이프로 놓을 수 있는지 확인하고 놓을 수 있으면 큐에 삽입

6. 현재 좌표가 (n-1, n-1)에 도달하면 cnt++ (본인은 입력 배열을 0부터 받았으므로 n-1)

 

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define MAX 16

using namespace std;

int N;
int cnt;
int house[MAX][MAX];

void movePipe() {
	queue<pair<pair<int, int>, int>> q;
	q.push({{0, 1}, 1}); // 처음 파이프는 항상 가로 파이프
	
	while(!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int dir = q.front().second; // 파이프의 방향: 1 가로 2 세로 3 대각선 
		q.pop();
		
		// 현재 좌표가 (n-1, n-1)에 도달하면   
		if(x == N-1 && y == N-1)
			cnt++;
		
		// 가로 파이프이면  
		if(dir == 1) {
			// 가로 파이프로 놓을 수 있는지 확인 
			if(y+1<N && house[x][y+1] == 0)   
				q.push({{x, y+1}, 1});
			
			// 대각선 파이프로 놓을 수 있는지 확인
			if(x+1<N && y+1<N) { 
				if(house[x][y+1] == 1 || house[x+1][y] == 1 || house[x+1][y+1] == 1)
					continue;
			 
				q.push({{x+1, y+1}, 3});
			}  
		}
		
		// 세로 파이프이면 
		else if(dir == 2) {
			// 세로 파이프로 놓을 수 있는지 확인  
			if(x+1<N && house[x+1][y] == 0)
				q.push({{x+1, y}, 2}); 
			
			// 대각선 파이프로 놓을 수 있는지 확인 
			if(x+1<N && y+1<N) { 
				if(house[x+1][y] == 1 || house[x+1][y+1] == 1 || house[x][y+1] == 1)
					continue;
			
				q.push({{x+1, y+1}, 3});  	
			}
		}
		
		// 대각선 파이프이면  
		else if(dir == 3) {
			// 가로 파이프로 놓을 수 있는지 확인 
			if(y+1<N && house[x][y+1] == 0)
				q.push({{x, y+1}, 1}); 
		
			// 세로 파이프로 놓을 수 있는지 확인 
			if(x+1<N && house[x+1][y] == 0)
				q.push({{x+1, y}, 2}); 
			
			// 대각선 파이프로 놓을 수 있는지 확인 
			if(x+1<N && y+1<N) {
				if(house[x+1][y] == 1 || house[x+1][y+1] == 1 || house[x][y+1] == 1)
					continue;
				
				q.push({{x+1, y+1}, 3});  
			}
		} 
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			cin>>house[i][j];
	
	movePipe(); // 파이프 옮기기  
	cout<<cnt;
			
	return 0;
}

 

 

 

 

baekjoon - 정답 화면

 

 

 

 

 

DFS 설명

 

 

 

《문제 풀이》

 

1. 집의 상태를 배열로 입력 받고 파이프 옮기기

2. 처음 파이프의 끝은 (0, 1)에 가로 방향으로 놓여있으므로 movePipe(0, 1, 0) <-- 마지막 0은 가로 방향이라는 의미

3. 가로 방향인 경우 파이프를 세로 방향으로 놓는 것은 불가능 (반대도 마찬가지)

4. 대각선 방향의 파이프인 경우에는 추가적으로 두개의 칸이 모두 벽인지 확인

5. movePipe(nx, ny, i) 를 통해 반복 

 

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define MAX 16

using namespace std;

int N;
int cnt;
int house[MAX][MAX]; 

typedef struct {
	int x, y;
}box;

// 가로 세로 대각선  
box moveD[3] = { {0, 1}, {1, 0}, {1, 1} };

void movePipe(int x, int y, int dir) {
	if(x == N-1 && y == N-1) {
		cnt++;
		return;
	}
	
	for(int i=0; i<3; i++) {
		
		// 가로 -> 세로 / 세로 -> 가로 불가능  
		if((i == 0 && dir == 1) || (i == 1 && dir == 0))
			continue;
		
		int nx = x + moveD[i].x;
		int ny = y + moveD[i].y;
		
		// 가로, 세로, 대각선 파이프의 공통적인 조건 확인  
		if(N<=nx || N<=ny || house[nx][ny] == 1)
			continue;
		
		// 대각선 파이프인 경우 추가 확인   
		if(i == 2 && (house[nx][ny-1] == 1 || house[nx-1][ny] == 1))
			continue;
			
		movePipe(nx, ny, i);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			cin>>house[i][j];
	
	movePipe(0, 1, 0); // 파이프 옮기기  
	cout<<cnt;
	
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면

 

 

 

 

공감과 댓글 부탁드려요 😊