BOJ-17070 파이프 옮기기

Seok·2020년 12월 6일

algorithm boj

Algorithm

목록 보기

7/60

첫 번째 방법

필요한 지식

BFS
시뮬레이션

접근

이 문제는 1년전 즈음 시험 볼 당시 문제를 똑바로 읽지 않아 3가지 이동방향이 아닌 8 방향으로 내마음 대로 해석하고 총 24가지의 경우를 작성해 버렸던 문제이다.
다시는 그런 실수 안해야지

파이프의 뒤,앞 2개의 좌표를 가진 구조체를 선언하고 사용
가로에선 가로, 대각
세로에선 대각, 세로
대각에선 가로, 세로, 대각
으로 이동이 가능하다. 모든 경우를 큐에 넣어주고 탐색한다.

코드(C++)

#include <iostream>
#include <queue>
using namespace std;
int map[16][16], n;
typedef struct Point {
	int y1, x1, y2, x2;
}point;
int ans = 0, dir[3][2] = { {0,1},{1,1},{1,0} };//가로,대각,세로
queue<point>q;
bool chk(point s, int f) {
	if (s.x2 >= n || s.y2 >= n) return false;
	if (f == 1 && !map[s.y1][s.x1] && !map[s.y2][s.x2] && !map[s.y1][s.x2] && !map[s.y2][s.x1]) return true;
	if (f != 1 && !map[s.y1][s.x1] && !map[s.y2][s.x2]) return true;
	return false;
}
int bfs() {
	q.push(point{ 0,0,0,1 });
	while (!q.empty()) {
		auto cur = q.front();
		q.pop();
		if (cur.y2 == n - 1 && cur.x2 == n - 1) {
			ans += 1;
			continue;
		}
		point next = point{ cur.y2,cur.x2,0,0 };
		//가로
		if (cur.y1 == cur.y2) {
			for (int k = 0; k <= 1; k++) {
				next.y2 = cur.y2 + dir[k][0];
				next.x2 = cur.x2 + dir[k][1];
				if (chk(next, k)) q.push(next);
			}
		}
		//세로
		else if (cur.x1 == cur.x2) {
			for (int k = 1; k <= 2; k++) {
				next.y2 = cur.y2 + dir[k][0];
				next.x2 = cur.x2 + dir[k][1];
				if (chk(next, k)) q.push(next);
			}
		}
		//대각
		else if (cur.x1 != cur.x2 && cur.y1 != cur.y2) {
			for (int k = 0; k <= 2; k++) {
				next.y2 = cur.y2 + dir[k][0];
				next.x2 = cur.x2 + dir[k][1];
				if (chk(next, k)) q.push(next);
			}
		}
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> map[i][j];
	cout << bfs();
	return 0;
}

두 번째 방법

필요한 지식

백트래킹

접근

다른방법으로 백트래킹을 사용할 수 있다.
+위의 방법에서 생각해보니 파이프의 뒷부분은 단지 기존의 앞부분의 위치로만 이동한다 따라서 뒷부분은 신경쓰지않아도 된다..

뒷 부분의 좌표정보를 지우고, 백트래킹을 사용했다. 위의 접근방법과 같이 가로 대각 세로 상태일때 진행가능한 부분만 잘 신경써주면 된다.

코드(C++)

#include <iostream>
using namespace std;
int map[16][16], n, ans = 0, dir[3][2] = { {0,1},{1,1},{1,0} };//가로,대각,세로
void dfs(int y, int x, int z) {
	if (y == (n - 1) && x == (n - 1)) {
		ans += 1;
		return;
	}
	for (int k = 0; k < 3; k++) {
		//가로상태에서 세로로 세로상태에서 가로로 못감
		if ((z == 0 && k == 2) || (z == 2 && k == 0)) continue;
		int ny = y + dir[k][0], nx = x + dir[k][1];
		if (ny >= n || nx >= n || map[ny][nx]) continue;
		//대각인경우 좌우 체크
		if (k == 1 && (map[y+1][x] || map[y][x+1])) continue;
		dfs(ny, nx, k);
	}
	return;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> map[i][j];
	dfs(0, 1, 0);
	cout << ans;
	return 0;
}