boj, 백준) 5231. 과외맨 ( C / C++)

1. 문제 링크

www.acmicpc.net/problem/5213

5213번: 과외맨

2. 문제 개요

출처 https://www.acmicpc.net/problem/5213

위 그림의 가장 왼쪽 위에서 출발하여 가장 오른쪽 밑의 타일까지 이동하는데 최단경로를 구하시오.

가장 오른쪽 밑까지 도달할 수 없으면 타일번호가 가장 큰 곳으로의 경로를 출력.

 

3. 문제 힌트

BFS로 최단 경로를 구하는 문제,

 

(1) 1개의 타일이 2개의 블록으로 이루어져 있다고 했을 때, 타일의 개수가 가장 적게 드는 경로가 최단경로임.  블록의 개수가 아님. 그래서 BFS를 진행할 때, 처음 탐색하는 타일이라면 2개의 블록 모두 queue에 넣어주어야 함.

 

(2) BFS의 특성상 도착하면 그것이 최단시간만에 도착한 것이기 때문에, 처음 도착하여 방문 처리할 때 어느 타일에서 왔는지, 이전 타일을 기록하면 경로를 도착 지점에서 출발지 까지 구할 수 있다.

4. 문제 풀이

이전 경로찾는 배열의 크기를 잘못 설정하여 맞는데 왜 틀렸지만 몇 시간 했던 문제..

보통 몇시간동안 도무지 어디가 틀렸는지 모를 땐, 구글에서 힌트를 조금 얻는데, 이 문제는 뭔가 좀 짜증이 나는 문제여서 힌트 보기가 싫었다. 꼭 찾아내고야 말겠다는..

 

문제 풀이로 넘어가서.

우선 실수할법한 반례를 제시하면,

5
1 1
1 4
4 4
4 4
4 5
3 1
1 3
5 5
6 4
2 2
3 1
2 2
1 6
5 5
3 1
1 3
5 1
3 3
2 2
1 6
6 1
1 1
1 3

위 처럼 나타낼 수 있다.

 

처음에 했던 착각인데, '타일' 기준으로 하지 않고 '블록'기준으로 한다면, 빨간색의 경로를 뱉는다. 왜냐하면 빨간색 경로는 블록의 개수가 15개이고, 파란색 경로는 17개이기 때문이다.

 

하지만 정답은 타일의 개수를 기준으로 하기 때문에 파란 색선으로 나타낸 경로를 출력해야 한다. 왜냐하면 빨간색 경로의 타일의 개수는 11개, 파란색 경로의 타일의 개수는 10개이기 때문이다.

 

그래서, BFS를 할 때, 타일 내부의 블록 이동을 제거해주기 위해서 타일에 처음 방문하는 순간 2개 블록을 모두 queue에 삽입하는 방법으로 해결할 수 있다.

 

 

그 외, 데이터 표현에 있어서, 위의 예처럼 블록의 값을 나타내었고,

똑같은 크기의 배열을 또 선언해서 tile의 번호를 저장하도록 하였다.

 

path관련해서는 3의 문제 힌트와, 코드를 보는 것이 더 이해가 잘 될 것 같다.

중요한 것은 타일의 개수가 최대 N * N - N / 2개라는 것이다.

왜 N/2 * N으로 생각했는지 모르겠지만,, 크기를 잘못 선언해서 시간을 많이 잡아먹었다.

배열 개수가 틀렸다면 당연히 런타임 에러를 뱉을 줄 알았건만.. ㅠ

 

5. 코드

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

struct COORD {
	COORD() {}
	COORD(int y_, int x_) :y(y_), x(x_) {}
	int y, x;
};
int map[500][1000], tilenum[500][1000];
int parent[250001];	
int n, maxtile;
queue<COORD> q;
bool visited[500][1000];
const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };
vector<int> ans;

int main()
{
	scanf("%d", &n);

	int num = 0;	//will be the number of last tile
	for (int i = 0; i < n; ++i) {
		if (i % 2 == 0) {
			for (int j = 0; j < 2 * n; j += 2) {
				scanf("%d %d", &map[i][j], &map[i][j + 1]);
				tilenum[i][j] = tilenum[i][j + 1] = ++num;
			}

		}
		else {
			for (int j = 1; j < 2 * n - 1; j += 2) {
				scanf("%d %d", &map[i][j], &map[i][j + 1]);
				tilenum[i][j] = tilenum[i][j + 1] = ++num;
			}
		}
	}

	q.push(COORD(0, 0));
	q.push(COORD(0, 1));
	visited[0][0] = true;
	visited[0][1] = true;
	parent[tilenum[0][0]] = 0;

	while (!q.empty()) {
		COORD cur = q.front(); q.pop();
		maxtile = max(maxtile, tilenum[cur.y][cur.x]);

		for (int dir = 0; dir < 4; ++dir) {
			COORD next;
			next.y = cur.y + dy[dir];
			next.x = cur.x + dx[dir];

			if (next.y < 0 || next.x < 0 || next.y >= n || next.x >= 2 * n || visited[next.y][next.x])
				continue;

			if (tilenum[next.y][next.x] != tilenum[cur.y][cur.x])
			{
				if (map[next.y][next.x] == map[cur.y][cur.x])
				{
					visited[next.y][next.x] = true;
					q.push(next);

					if (next.y % 2 == 0) {
						if (next.x % 2 == 0) {
							visited[next.y][next.x + 1] = true;
							q.push(COORD(next.y, next.x + 1));
						}
						else
						{
							visited[next.y][next.x - 1] = true;
							q.push(COORD(next.y, next.x - 1));
						}
					}
					else
					{
						if (next.x % 2 == 0) {
							visited[next.y][next.x - 1] = true;
							q.push(COORD(next.y, next.x - 1));
						}
						else
						{
							visited[next.y][next.x + 1] = true;
							q.push(COORD(next.y, next.x + 1));
						}
					}

					if (parent[tilenum[next.y][next.x]] == 0)
						parent[tilenum[next.y][next.x]] = tilenum[cur.y][cur.x];
				}
			}
			else
			{
				visited[next.y][next.x] = true;
				q.push(next);
			}
		}
	}

	for (int i = maxtile; i != 0; i = parent[i])
		ans.push_back(i);

	printf("%d\n", ans.size());
	for (int i = ans.size() - 1; i >= 0; --i)
		printf("%d ", ans[i]);

	return 0;
}

6. 결과