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

문제

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

17070번: 파이프 옮기기 1

 

문제이해

• 첫째 줄에 N을 입력한다.
• 두번째 줄부터 N x N 크기의 집의 상태를 입력한다. 빈칸은 0이며 벽은 1로 입력한다.
• (1, 1), (1, 2)에 위치해 있는 파이프를 (N, N)까지 이동시키는 방법의 수를 구해 출력한다.

 

이 문제에서 주의해야 할 점은 현재 파이프의 방향에 따라 파이프를 옮길 수 있는 방법이 정해져있다는 것이다.

 

파이프가 가질 수 있는 모양은 총 3개가 있으며 가로로 있는 파이프는 1로 표시하고 세로로 있는 파이프는 2로 표시하며 대각선으로 있는 파이프는 3으로 표시하였다. 파이프의 (1, 2)를 머리라고 생각하고 (1, 2)가 (N, N)까지 이동하는 것에 대한 너비우선탐색(BFS)를 사용하면 된다. 파이프의 꼬리(1, 1)는 항상 머리가 지나간 위치에 있기 때문에 꼬리가 집 밖으로 나간다던가 벽으로 들어가는 걱정은 할 필요가 없으며 파이프가 가지고 있는 방향 따라 저절로 위치가 바뀌게 하면 된다.

꼬리는 크게 중요하지 않은 요소이다. 머리의 좌표와 현재 파이프의 방향만 확인하면 된다.

 

다음은 BFS를 통해 백준 17070번 파이프 옮기기 1을 해결한 코드이다.

 

문제풀이

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> map;
int N, X;

int bfs() {
	int count{};
	queue<pair<pair<int, int>, int>> pipe;
	pipe.push(make_pair(make_pair(0, 1), 1));
	visited[0][1] = true;
    while (!pipe.empty()) {
        pair<pair<int, int>, int> top = pipe.front();
        pipe.pop();
        if (top.first.first == N - 1 && top.first.second == N - 1) {
            count++;
        }
        int newFirst = top.first.first;
        int newSecond = top.first.second;

        if (top.second == 1) {
            if (newSecond + 1 < N && map[newFirst][newSecond + 1] != 1) {
                pipe.push(make_pair(make_pair(newFirst, newSecond + 1), 1));
                if (newFirst + 1 < N && map[newFirst + 1][newSecond] != 1 
                && map[newFirst + 1][newSecond + 1] != 1) {
                    pipe.push(make_pair(make_pair(newFirst + 1, newSecond + 1), 3));
                }
            }
        }
        else if (top.second == 2) {
            if (newFirst + 1 < N && map[newFirst + 1][newSecond] != 1) {
                pipe.push(make_pair(make_pair(newFirst + 1, newSecond), 2));
                if (newSecond + 1 < N && map[newFirst][newSecond + 1] != 1 
                && map[newFirst + 1][newSecond + 1] != 1) {
                    pipe.push(make_pair(make_pair(newFirst + 1, newSecond + 1), 3));
                }
            }
        }
        else if (top.second == 3) {
            if (newFirst + 1 < N && map[newFirst + 1][newSecond] != 1) {
                pipe.push(make_pair(make_pair(newFirst + 1, newSecond), 2));
                if (newSecond + 1 < N && map[newFirst][newSecond + 1] != 1) {
                    pipe.push(make_pair(make_pair(newFirst, newSecond + 1), 1));
                    if (map[newFirst + 1][newSecond + 1] != 1) {
                        pipe.push(make_pair(make_pair(newFirst + 1, newSecond + 1), 3));
                    }
                }

            }
            else if (newSecond + 1 < N && map[newFirst][newSecond + 1] != 1) {
                pipe.push(make_pair(make_pair(newFirst, newSecond + 1), 1));
                if (newFirst + 1 < N && map[newFirst + 1][newSecond] != 1) {
                    pipe.push(make_pair(make_pair(newFirst + 1, newSecond), 2));
                    if (map[newFirst + 1][newSecond + 1] != 1) {
                        pipe.push(make_pair(make_pair(newFirst + 1, newSecond + 1), 3));
                    }
                }
            }
        }
    }
	return count;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N;
	for (int i{ 0 }; i < N; i++) {
		vector<int> floor(N);
		for (int a{ 0 }; a < N; a++)
			cin >> floor[a];
		map.push_back(floor);
	}
	cout << bfs();
}

현재 파이프의 방향에 따라 이동가능한 공간을 파악하고 bfs에 넣어주는 식으로 bfs를 만들었다. 파이프가 전에 갔던 곳을 다시 갈 이유는 없기 때문에 방문 표시는 사용하지 않았다.

 

문제후기

bfs를 사용하면 쉽게 해결되는 문제였다.