취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24819번 문제인 Escape Wall Maria이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어지는 grid의 각 cell을 노드로, 서로 이동가능한 인접한 노드 사이에 에지를 집어넣은 그래프를 생각해보자. 'S'가 써진 지점에서 각 노드까지 최단시간으로 갈 수 있는 시간을 구하는 것으로 문제를 해결할 수 있다.

특히 이 문제에서는 어떤 방향으로 이동해도 한 칸 움직이는 시간은 일정하므로 BFS를 이용해 문제를 해결할 수 있다.

각 방향 움직임과 그 때 이동하려는 칸에 써져있어도 되는 문자(U,D,L,R)를 배열로 잘 구성해 편하게 구현하자.

아래는 제출한 소스코드이다.

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

int T, R, C;
int startR, startC;
string board[100];
int dist[100][100];
bool visited[100][100];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };
char dir[4] = { 'U','D','L','R' };

void bfs() {
	queue<pair<int, int>> que;
	visited[startR][startC] = 1;
	que.push(make_pair(startR * C + startC, 0));

	while (!que.empty()) {
		int curR = que.front().first / C, curC = que.front().first % C, curD = que.front().second;
		que.pop();
		dist[curR][curC] = curD;
		for (int i = 0; i < 4; i++) {
			int rr = curR + dr[i], cc = curC + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (visited[rr][cc]) continue;
			if (board[rr][cc] == '0' || board[rr][cc] == dir[i]) {
				visited[rr][cc] = 1;
				que.push(make_pair(rr * C + cc, curD + 1));
			}
		}
	}
}

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

	cin >> T >> R >> C;
	for (int r = 0; r < R; r++) {
		string& tmp = board[r];
		cin >> tmp;
		for (int c = 0; c < C; c++) {
			if (tmp[c] == 'S') startR = r, startC = c;
		}
	}

	bfs();

	int ans = 1000000007;
	for (int r = 0; r < R; r++) {
		if (visited[r][0]) ans = min(ans, dist[r][0]);
		if (visited[r][C - 1]) ans = min(ans, dist[r][C - 1]);
	}
	for (int c = 0; c < C; c++) {
		if (visited[0][c]) ans = min(ans, dist[0][c]);
		if (visited[R - 1][c]) ans = min(ans, dist[R - 1][c]);
	}

	if (ans > T) cout << "NOT POSSIBLE";
	else cout << ans;
}