[ Baekjoon ] 17070. 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

풀이 방법

파이프의 양 끝의 위치와 놓여진 방향을 pipe라는 구조체에 저장한다.

struct pos{
	int r;
	int c;
	pos(int r_, int c_): r(r_), c(c_) {};
};

struct pipe{
	pos start;
	pos end;
	int dir;
	pipe(pos start_, pos end_, int dir_): start(start_), end(end_), dir(dir_) {};
};

 

num_routes()

(0, 0)~(0, 1)에 걸쳐진 파이프가 움직일 수 있는 모든 경우의 수를 DFS로 구하여 (N-1, N-1)에 도착하는 경우의 수를 카운트한다. 스택을 사용하면 DFS를 구현할 수 있다. 

 

처음에는 큐를 사용해 BSF를 구현했는데, N이 커질수록 큐의 크기도 exponential하게 늘어나 런타임 에러가 발생했다. 따라서 해당 문제에서는 DFS를 이용하는 게 적절하다.

 

파이프를 옮길 때에는 다음과 같이 다음 위치의 파이프를 구한다.

enum {RIGHT, CROSS, DOWN};

const int dr[3] = {0, 1, 1}; // RIGHT, CROSS, DOWN
const int dc[3] = {1, 1, 0};

// move to i-th direction
pipe next = {cur.end, pos(cur.end.r+dr[i], cur.end.c+dc[i]), i};

 

전체 코드는 여기서 확인할 수 있다.