[BOJ/Gold 5] 백준 31671 특별한 오름 등반(C++)

문제 링크

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

 

문제

오름은 올라야만 한다.

 

 

NLCS Jeju의 기숙사 이름 "오름"은 제주에서 봉우리나 산을 부르는 말인 오름에서 따왔다. 각 기숙사의 학생들은 1년에 한 번, 실제로 기숙사 이름의 기원인 오름을 오르게 된다.

오름은 xy 평면에서 세 점 (0, 0), (N, N), (2N, 0)을 잇는 삼각형 모양이다. 당신은 (0, 0)에서 출발해서 (2N, 0)에 도착해야 한다.

이동할 때는 (x, y)에서 (x + 1, y + 1) 혹은 (x + 1, y − 1)로만 이동할 수 있다. 또한 이동하여 도착한 위치는 오름의 내부 혹은 경계여야 한다.

오름에서 길을 잃기 쉽기 때문에 길을 잃기 쉬운 M개의 지점에 선생님들이 계신다. 하지만 숙제를 하지 않은 당신은 선생님과 만나는 것이 부담스럽기 때문에 선생님을 피해서 이동해야 한다.

또한 당신은 오름 등산을 특별한 기억으로 남기기 위해 사진을 찍기로 했다. 사진의 아름다움은 사진을 찍은 높이가 높을수록 커진다. 정확하게는 사진을 찍은 y좌표가 그 사진의 아름다움 수치가 된다.

얼마나 아름다운 사진을 찍을 수 있을지 구해보자.

 

입력

첫 번째 줄에 오름의 높이 N과 선생님이 계시는 지점의 개수 M이 공백을 사이에 두고 주어진다.

두 번째 줄부터 M+1번째 줄까지 선생님의 x좌표 xi와 y좌표 yi가 공백으로 구분되어 주어진다. 선생님은 항상 오름의 내부 혹은 경계에 있다.

 

출력

첫 번째 줄에 찍을 수 있는 사진의 아름다움의 최댓값을 출력한다. 단, 시작 지점에서 도착 지점까지 이동할 수 없는 경우에는 -1을 출력한다.

 

제한

•  1 ≤ N ≤ 1,000
•  0 ≤ M ≤ min((n+1)(n+2)/2−1, 100000)
•  0 ≤ xi ≤ 2N
•  0 ≤ yi ≤ N
•  xi + yi는 짝수다.
•  (0, 0)에는 선생님이 계시지 않는다.

 

예제 입력 1

4 3
2 2
4 0
5 3

예제 출력 1

2

예제 입력 2

3 1
3 1

예제 출력 2

3

예제 입력 3

3 1
1 1

예제 출력 3

-1

 

알고리즘 분류

• 그래프 탐색

 

풀이

(0, 0)에서 BFS를 시작하고 (0, 2N)에서 BFS를 시작한다.

두 번의 BFS를 하면서 두 번 다 도달할 수 있는 점들 중 최대 높이를 구한다.

다만 (0, 0)에서 (0, 2N)으로 도달할 수 없거나, (0, 2N)에서 (0, 0)으로 도달할 수 없는 경우 -1을 출력한다.

2번의 BFS를 하면서 2번 다 방문한 점이 없으면 -1을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, X, Y;
int MAP[MAX][MAX * 2];
bool Visited1[MAX][MAX * 2];
bool Visited2[MAX][MAX * 2];
int MoveY[2] = { 1,-1 };
int Answer = -1;

void input() {
	cin >> N >> M;
	while (M--) {
		cin >> X >> Y;
		MAP[Y][X] = -1;
	}
}

void bfs1() {
	queue<pair<int, int> > Q;
	Visited1[0][0] = true;
	Q.push(make_pair(0, 0));

	while (!Q.empty()) {
		int NowY = Q.front().first;
		int NowX = Q.front().second;
		Q.pop();

		for (int i = 0; i < 2; i++) {
			int NextY = NowY + MoveY[i];
			int NextX = NowX + 1;

			if ((NextY < 0) || (NextY > N) || (NextX < 0) || (NextX > (2 * N))) {
				continue;
			}

			if (NextX <= N) {
                if ((NextY < 0) || (NextY > NextX)) {
				    continue;
                }
			}
            else if ((NextX > N) && (NextX <= (2 * N))) {
                if ((NextY < 0) || (NextY > (2 * N) - NextX)) {
				    continue;
                }
            }

			if (Visited1[NextY][NextX]) {
				continue;
			}

			if (MAP[NextY][NextX] == -1) {
				continue;
			}
			
			Q.push(make_pair(NextY, NextX));
			Visited1[NextY][NextX] = true;
		}
	};
}

void bfs2() {
	queue<pair<int, int> > Q;
	Visited2[0][2 * N] = true;
	Q.push(make_pair(0, 2 * N));

	while (!Q.empty()) {
		int NowY = Q.front().first;
		int NowX = Q.front().second;
		Q.pop();

		for (int i = 0; i < 2; i++) {
			int NextY = NowY + MoveY[i];
			int NextX = NowX - 1;

			if ((NextY < 0) || (NextY > N) || (NextX < 0) || (NextX > (2 * N))) {
				continue;
			}

			if ((NextX >= 0) && (NextX <= N)) {
                if ((NextY < 0) || (NextY > NextX)) {
				    continue;
                }
			}
            else if (NextX > N) {
                if ((NextY < 0) || (NextY > (2 * N) - NextX)) {
				    continue;
                }
            }

			if (Visited2[NextY][NextX]) {
				continue;
			}

			if (MAP[NextY][NextX] == -1) {
				continue;
			}
			
			Q.push(make_pair(NextY, NextX));
			Visited2[NextY][NextX] = true;
		}
	};
}

void settings() {
    bfs1();
    bfs2();
}

void find_Answer() {
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= (2 * N); j++) {
            if (Visited1[i][j] && Visited2[i][j]) {
                Answer = max(Answer, i);
            }
        }
    }
    if (Visited1[0][2 * N] && Visited2[0][0]) {
	    cout << Answer << "\n";
    }
    else {
        cout << "-1\n";
    }
}

int main() {
	FASTIO
	input();
    settings();
	find_Answer();

	return 0;
}