Baekjoon 17070 파이프 옮기기 1

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

소스결과 8516 KB / 104 ms

출처 Baekjoon

언어 C++ 17

분류 BFS DFS

 

설명

시작 지점에서 가로로 놓여있는 파이프를 연결해 목적지에 연결 할 수 있도록 파이프를 배치 하는 방법의 가지 수를 출력해주자.

 

이번 삼성 A형 1번 문제에서 몇가지 조건이 빠진 문제다. 나머지 조건은 똑같다. 크게 다른 점이라면 문제가 조금 친절한 점 정도일까..

파이프를 놓을 수 있는 방법은 3가지 존재한다. 그리고 파이프를 연결 하는 부분에 있어서 45도 이상 돌릴 수 없다. 가로로 놓인 파이프 뒤에 바로 세로를 놓을 수는 없다.

가로와 세로로 놓을 때에는 칸만 조사하지만, 대각선으로 놓는 경우는 3칸을 조사 해야한다. 시작과 끝이 명확하기 때문에 함수로 빼놓으면 된다.

기준이 되는 지점은 파이프의 머리 부분을 기준으로 하고, 파이프 정보에는 파이프가 바라보는 방향을 같이 저장한다.

 

BFS와 DFS 2가지가 있지만 시간제한이 0.5초인 점으로 보아하니 BFS만 성공할 것 같다. 소스코드는 BFS로 해결 했다.

 

알고리즘

1. 시작 지점을 (1, 0)으로 시작하며 방향을 가로로 놓는다.

2. 현재 놓인 파이프를 기준으로 놓을 수 있는 범위, 장애물 여부, 방향 여부 3가지를 판단해 놓을 수 있는 경우 Queue에 넣는다.

3. 현재 파이프의 머리 부분이 목적지에 위치하는경우 결과 값을 1 늘린다.

4. Queue가 빌 때 까지 반복한다.

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

const short MAX = 32;

bool board[MAX][MAX];
int n;
const short posX[3] = { 1, 0, 1 };
const short posY[3] = { 0, 1, 1 };

struct Point {
	short x, y;
	short look;

	Point(short x, short y, short l) : x(x), y(y), look(l) {};
	Point();
};

bool checkAble(short sX, short sY, short eX, short eY)
{
	for (int i = sX; i <= eX; i++)
		for (int j = sY; j <= eY; j++)
			if (board[j][i])
				return false;
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int res = 0;
	queue<Point> q;

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> board[i][j];

	q.push(Point(1, 0, 0));

	while (!q.empty())
	{
		Point cur = q.front();
		q.pop();

		if (cur.x == n - 1 && cur.y == n - 1)
		{
			res++;
			continue;
		}

		for (int i = 0; i < 3; i++)
		{
			int nextX = cur.x + posX[i];
			int nextY = cur.y + posY[i];

			if (nextX >= n || nextY >= n || (cur.look == 0 && i == 1) || (cur.look == 1 && i == 0))
				continue;

			if (checkAble(cur.x, cur.y, nextX, nextY))
				q.push(Point(nextX, nextY, i));
		}
	}

	cout << res;

	return 0;
}