[백준 5213] 과외맨 (C++)

문제 링크: https://www.acmicpc.net/problem/5213

5213번: 과외맨

1. 주의할 점

- 타일 1개에는 2개의 원소가 포함된다

- N의 범위가 500이하이므로 최대범위는 501까지로 설정한다 -> 이 부분 설정 안해서 한번 더 틀렸다.

- 구조체를 이용해서 메모리를 최소화하자(배열의 범위가 커서 메모리 초과가 날 수 있다) -> 이미 한번 메모리 초과의 결과가 떴다.

- 마지막 줄의 타일로 이동할 수 없는 경우엔 번호가 가장 큰 타일로 이동한다.

 

2. 구현

- BFS를 통해 최단경로를 찾는다

- BFS를 진행하면서 마지막 줄의 마지막 타일에 도달하지 못하는 경우를 고려하여 가장 큰 타일 번호를 새로운 타일이 추가될 때 마다 갱신한다

- 이전의 경로를 저장하기 위해 Before배열을 사용한다

- BFS 진행중에 타일의 다음으로 검색하는 타일이 타일의 왼쪽부분인지 오른쪽 부분인지에 대한 고려도 필요하다

  오른쪽이면 추가적으로 왼쪽을 검사하고 왼쪽이면 추가적으로 오른쪽을 검사한다

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
struct info {
	int x, y;
};
info tmp;
struct info2 {
	int tile, val, dist;
};
info2 arr[501][501*2];
int before[501*501];			//이전 값
int num, s, e, r = 0, c = 0, maxi = 0, cnt = 1;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

void path() {
	vector<int> v;
	v.push_back(maxi);
	while (before[maxi]!=0) {
		maxi = before[maxi];
		v.push_back(maxi);
	}
	cout << v.size() << '\n';
	for (int i = v.size() - 1; i >= 0; i--)
		cout << v[i] << " ";
}

void bfs() {
	queue<info> q;
	tmp.x = 0;
	tmp.y = 0;
	q.push(tmp);
	tmp.x = 1;
	q.push(tmp);
	arr[0][0].dist = 1;
	arr[0][1].dist = 1;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx >= 0 && ny >= 0 && nx < 2 * num && ny < num && arr[ny][nx].val == arr[cy][cx].val) {
				if (arr[ny][nx].dist != 0) continue;		//이미 방문한 경우
				bool left = false;
				if (arr[ny][nx].tile == arr[ny][nx - 1].tile) left = true;	//왼쪽이 같은 타일
				arr[ny][nx].dist = arr[cy][cx].dist + 1;
				tmp.x = nx;
				tmp.y = ny;
				q.push(tmp);
				if (left) {			//왼쪽타일이 같음
					arr[ny][nx - 1].dist = arr[cy][cx].dist + 1;
					tmp.x = nx - 1;
					q.push(tmp);
				}
				else {				//오른쪽이 같음
					arr[ny][nx + 1].dist = arr[cy][cx].dist + 1;
					tmp.x = nx + 1;
					q.push(tmp);
				}
				//경로 갱신
				before[arr[ny][nx].tile] = arr[cy][cx].tile;
				maxi = max(maxi, arr[ny][nx].tile);
			}
		}
	}
}

int main() {
	cin >> num;
	for (int i = 0; i < num*num - num / 2; i++) {
		cin >> s >> e;
		arr[r][c].val = s;
		arr[r][c + 1].val = e;
		arr[r][c].tile = cnt;
		arr[r][c + 1].tile = cnt++;
		c += 2;
		if (r % 2 == 0 && c == 2 * num) {
			r += 1;
			c = 1;
		}
		else if (r % 2 == 1 && c == 2 *num - 1) {
			r += 1;
			c = 0;
		}
	}
	bfs();
	path();
	system("pause");
	return 0;
}