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

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

17070번: 파이프 옮기기 1

 

문제 이해

(1,1)에서 (N,N)까지 가는 모든 경로를 탐색해야하기 때문에 BFS를 쓰던 DFS를 쓰던 상관이 없다.

근데 나는 BFS를 사용했다.

 

파이프는 hy, hx, ty, tx 네 개의 변수로 형상화했다.

파이프의 머리와 꼬리를 각각 (hy, hx), (ty, tx)로 만든거다.

그래서 파이프가 움직일 때 머리는 [방향벡터 + 기존 머리 좌표] 로 잡아주면 되고 꼬리는 [기존 머리 좌표] 로 바꿔주면 된다.

typedef struct st {
	int hy, hx, ty, tx;
	int dir;
}ELE;

이 파이프의 좌표를 모두 큐의 구조체로 넣어주고, 더불이 dir라는 현재 파이프의 방향을 구조체로 만들어주었다.

주어진 세 방향으로 움직여야 하는데, 

int go[3][3] = { { 1, 1, 0 }, {1, 1, 1}, {0, 1, 1} }; // →, ↘, ↓

파이프의 방향에 따라 갈 수 있는 방향을 go라는 배열에 정리해두었고,

BFS에서 다음 좌표를 찾을 때 go를 참고하도록 했다.

 

이렇게 파이프가 움직이다가 도착지에 도착하면 cnt 를 증가시켜서 경로 개수를 추가해주면 된다.

모든 경로 (경우의 수)를 봐야하기 때문에 visited 배열은 사용하지 않는다. 

 

BFS 자체는 어렵지 않은데,

파이프가 대각선으로 움직일 때 가로나 세로로 움직일 때마다 확인해야 하는 빈칸이 더 많다.

처음에 그걸 제대로 안해서 틀렸었다. 고치니 바로 성공이었다.

 

전체 코드

#include <stdio.h>
#include <string.h>
#define MAXN 16

int N;
int map[MAXN + 5][MAXN + 5];
//int hy, hx, ty, tx; // 파이프 head, tail 좌표
//int dir = 0; // 가로 방향
int cnt;

int dy[] = { 0, 1, 1 }; // →, ↘, ↓
int dx[] = { 1, 1, 0 };
int go[3][3] = { { 1, 1, 0 }, {1, 1, 1}, {0, 1, 1} }; // →, ↘, ↓

typedef struct st {
	int hy, hx, ty, tx;
	int dir;
}ELE;
ELE q[MAXN * MAXN * 100000]; // 큐사이즈를 엄청 크게 줘야 함!
int wp, rp;
void enq(int hy, int hx, int ty, int tx, int dir) {
	q[wp].hy = hy, q[wp].hx = hx;
	q[wp].ty = ty, q[wp].tx = tx;
	q[wp++].dir = dir;
}
ELE deq(void) { return q[rp++]; }
int empty(void) { return wp == rp; }

void Get_Input(void) {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}

void BFS(void) {

	int nhy, nhx, nty, ntx;
	enq(1, 2, 1, 1, 0);
	while (!empty()) {
		ELE cur = deq();
		for (int i = 0; i < 3; i++) {
			if (go[cur.dir][i] == 0) continue;
			nty = cur.hy, ntx = cur.hx;
			nhy = cur.hy + dy[i];
			nhx = cur.hx + dx[i];
			if (nhy < 1 || nhy > N || nhx < 1 || nhx >N) continue;
			if (map[nhy][nhx] == 1) continue;
			if (i == 1) {
				if (map[nhy - 1][nhx] == 1 || map[nhy][nhx - 1] == 1) continue;
			}
			if (nhy == N && nhx == N) { // 도착
				cnt++;
				continue;
			}
			enq(nhy, nhx, nty, ntx, i);
		}
	}
	
}


int main(void) {
	Get_Input();
	BFS();
	printf("%d", cnt);
	return 0;
}