[백준OJ] 17070번 파이프 옮기기

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

---

 

-풀이-

BFS를 이용하여, 도달할 수 있는 모든 경우를 구하였다.

기본적으로 움직일 수 있는 경우의 수가 겹칠 수 없는 3가지로 제한이 되어서, 그냥 가능한 모든 경우를 Queue에 넣어가며bfs를 실행해주었다.

기본적인 bfs를 실행하며 n-1, n-1에 도달했을때 answer++로 갱신시켜주면 되는데, 3번째 경우(대각선으로 움직이는 경우)는 queue에 넣어줄때, 해당 좌표의 왼쪽과 윗쪽도 벽이 아니여야 움직일 수 있는 조건을 추가해주는것을 조심해야 한다.

 

-시간복잡도-

모든 배열을 탐색하므로, O(N²)이 된다.

 

-코드-

 

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int n;
int maze[16][16];
int mv[3][2] = { {0,1},{1,0},{1,1} };

bool isIn(int i, int j) {
	return i >= 0 && i < n&&j >= 0 && j < n;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> maze[i][j];
		}
	}
	queue<pair<pair<int, int>,int>> q;
	q.push({ {0,1},0 });
	int answer = 0;
	while (!q.empty()) {
		int i = q.front().first.first;
		int j = q.front().first.second;
		int d = q.front().second;
		q.pop();
		if (i == n - 1 && j == n - 1) {
			answer++;
			continue;
		}
		for (int ii = 0; ii < 3; ii++) {
			if (d == 0 && ii == 1) continue;
			if (d == 1 && ii == 0) continue;
			int ni = i + mv[ii][0];
			int nj = j + mv[ii][1];
			if (isIn(ni, nj)&&maze[ni][nj]!=1) {
				if (ii == 2 && (maze[ni-1][nj] == 1 || maze[ni][nj-1] == 1)) continue;
				q.push({ {ni,nj},ii });
			}
		}
	}
	cout << answer << "\n";
	return 0;
}