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

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

17070번: 파이프 옮기기 1

#include <cstdio>
#include <queue>

int N;
int map_pipe[16 + 2][16 + 2];
int visited[16 + 2][16 + 2];

int dir_x[3] = { 0, 1, 1 };	// 우0 , 대1 , 하2
int dir_y[3] = { 1, 1, 0 };

struct _st
{
	int x;
	int y;
	int dir;
};

std::queue<_st> Q;

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


void go_right(int x, int y)	
{
	int nx = x + dir_x[0];
	int ny = y + dir_y[0];

	if (nx < 1 || nx > N || ny < 1 || ny > N) return;
	if (map_pipe[nx][ny]) return;

	Q.push({ nx, ny, 0 });
	return;
}


void go_diag(int x, int y)
{
	int nx = x + dir_x[1];
	int ny = y + dir_y[1];

	if (nx < 1 || nx > N || ny < 1 || ny > N) return;
	if (map_pipe[nx][ny]) return;
	if (nx - 1 < 1 || nx - 1 > N || ny - 1 < 1 || ny - 1 > N) return;
	if (map_pipe[nx][ny - 1] || map_pipe[nx - 1][ny]) return;

	Q.push({ nx, ny, 1 });
	return;
}


void go_down(int x, int y)
{
	int nx = x + dir_x[2];
	int ny = y + dir_y[2];

	if (nx < 1 || nx > N || ny < 1 || ny > N) return;
	if (map_pipe[nx][ny]) return;

	Q.push({ nx, ny, 2 });
	return;
}




int BFS()
{
	int cnt = 0;	// 방법의 수 세기
	Q.push({ 1, 2, 0 });	// 끝점 삽입, 방향은 우0

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		if (data.x == N && data.y == N) cnt++;

		switch (data.dir)
		{
		case 0:
			go_right(data.x, data.y);
			go_diag(data.x, data.y);
			break;
		case 1:
			go_right(data.x, data.y);
			go_diag(data.x, data.y);
			go_down(data.x, data.y);
			break;
		case 2:
			go_diag(data.x, data.y);
			go_down(data.x, data.y);
			break;
		}
	}
	return cnt;
}



int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

시험 전에 한 시간 자습줘서 풀었다 ㅋㅋ 

처음 코드 짰을 때 예제도 제대로 출력 안돼서 개짜증났었는데 갈아엎고 1트에 AC 받아서 키부니가 조크든요^-^

 

일단,, 문제를 잘읽어야 한다. 

모든 방향에서 오른쪽, 오른쪽 대각 아래쪽, 아래쪽 방향을 갈 수 있는 것은 아니다. 

만약 파이프가 놓여진 방향이 "가로"라면 "오른쪽, 오른쪽 대각 아래쪽" 밖에 가지 못한다. 

파이프가 놓여진 방향이 "세로"라면 "아래쪽, 오른쪽 대각 아래쪽" 밖에 가지 못한다. 

파이프가 놓여진 방향이 "대각선"이라면 "오른쪽, 아래쪽, 오른쪽 대각 아래쪽" 모든 방향으로 갈 수 있다. 

이걸 놓쳐서 삽질 좀 했다. 문제를 잘 읽자.. 관성대로 풀지 말자... 

 

 

// BFS( ) 함수 

상태 발전은 큐 Q에 끝점을 삽입하여 진행했다. 어차피 시작점은 볼 필요 없다. 

그리고 방금 큐에서 pop된 데이터가 (N, N)이라면 cnt 변수를 증가시켜주었다. 이때 return 하지 않은 이유는 (N, N)까지 도달하는 모든 방법의 개수를 구해주어야 하기 때문이다. 

 

파이프가 놓여진 방향을 기준으로 각각 다르게 진행해야 하기 때문에 큐에 삽입할 구조체의 원소에 type을 표시해주었다. 선언한 방향벡터(dir_x, dir_y)의 순서대로 0번이면 오른쪽, 1번이면 오른쪽 대각선 아래, 2번이면 아래쪽이다. 그리고 switch ~ case문을 사용하여 타입별로 진행할 수 있는 방향의 함수를 호출해주었다. 

 

 

// go_right( ), go_diag( ), go_down( ) 함수

각 방향별로 진행 예정인 좌표 (nx, ny)의 유효성 검사(영역 내부인지, 빈칸이어야 할 부분에 벽이 있지는 않은지)를 하고, 만약 모든 조건을 통과하면 상태 발전을 위해 큐에 삽입해준다. 

여기서 go_right( )와 go_down( ) 함수는 타입만 다르지 같은 역할을 하기 때문에 합치고 싶었는데, 파이프가 대각선으로 놓인 경우 모든 방향으로 진행될 수 있어서.. 이 경우 때문에 아직 좋은 방법을 생각해내진 못했다. 

(data.dir을 인자로 넘겨서 함수를 합치고 싶었음.. )