[백준] 17070번 - 파이프 옮기기 1

 

 

💡 깊이 우선 탐색 (DFS)

 

삼성 A형 기출문제라 해서 풀어봤는데, 

DFS로 손쉽게 풀 수 있는 알고리즘 문제였다.

 

먼저 파이프를 밀어 옮겨야하는 상황에서 파이프에 옮기는 방법은 가로 2가지, 세로 2가지, 대각선 3가지인데

DFS를 이용해 조건을 잘 맞추어 모든 상황을 고려해 만들어주면 된다.

 

• 가로인 경우 - (x,y+1), (x+1,y+1)

• 세로인 경우 - (x+1,y), (x+1,y+1)

• 대각선인 경우 - (x,y+1), (x+1,y), (x+1,y+1)

 

이때 주의할점은 옮겨야 할 곳이 1인 곳은 가지 못하도록 해줘야하는데 

가로와 세로는 각각 (x+1, y)와 (x, y+1)만 고려해주면 되지만 대각선은 (x-1,y) (x,y-1) (x,y), 총 3가지를 고려해줘야 한다.

 

✏️ 구현 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> adj;
int cnt = 0;
int N;

void dfs(int x, int y, int dir) {

	if (x >= 0 && y >= 0 && x < N && y < N) {
		
		if (dir == 2) {
			if (adj[x][y] == 1 || adj[x - 1][y] == 1 || adj[x][y - 1] == 1) {
				return;
			}
		}
		else if (dir == 1 || dir == 0) {
			if (adj[x][y] == 1) {
				return;
			}
		}

		if (x == N - 1 && y == N - 1) {
			cnt++;
			return;
		}

		

		if (dir == 0) {
			dfs(x, y + 1, 0);
			dfs(x + 1, y + 1, 2 );
		}
		else if (dir == 1) {
			dfs(x + 1, y, 1);
			dfs(x + 1, y + 1, 2);
		}
		else {
			dfs(x, y + 1, 0);
			dfs(x + 1, y, 1);
			dfs(x + 1, y + 1, 2);
		}
	}

	
}

int main() {
	
	cin >> N;
	
	adj = vector<vector<int>>(N, vector<int>(N, 0));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			int block;
			cin >> block;
			if(block ==1)
				adj[i][j] = block;		
		}
	}
	
	if (adj[0][0] != 1 && adj[N-1][N-1] != 1) {
		dfs(0, 1, 0);
	}

	cout << cnt;
}

 

✏️ 고려해야 할 테스트 케이스

 

1) (0,0)이 1인 경우

4
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

 

2) (N-1, N-1)이 1인 경우

4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1

 

 

3) 마지막의 파이프가 대각선일 때 (N-2,N-1) 또는 (N-1, N-2)가 1인 경우

 

4
0 0 0 0
0 0 0 0
0 0 0 1
0 0 1 0

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!