BOJ 17836

27 Jan 2020 • ProblemSolving

공주님을구해라!

문제출처

1.설계(7)

  • 문제 해석

    • N x M 배열에서 (1,1)좌표에서 시작하여 공주님위치(N,M)에 T시간 내에 도착하는 가장 빠른 시간을 구하는 문제입니다.
    • 배열에서 그람(검)을 찾은 경우에는 마법벽을 뚫고 이동할 수 있습니다.

  • 설계

    • 검을 찾지 않은 상태와 찾은 상태를 표현하기 위해 visited[N][M][2] 배열을 이용합니다.
    • 최소시간을 구하기 위해서 BFS를 이용하고 T시간동안 진행하게 됩니다.

2.구현(X)

  • 코드
#include <iostream>
#include <queue>
using namespace std;
#define MAXN 100

int N, M,T;
struct info {
	int x;
	int y;
	int found;
};
queue<info> q;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int map[MAXN][MAXN];
bool visited[MAXN][MAXN][2];

void bfs() {
	q.push({ 0,0,0 });
	visited[0][0][0] = true;
	int cnt = 0;
	
	
	for (int t = 0; t<=T; t++){
		int q_size = q.size();
		while (q_size--) {
			int x = q.front().x;
			int y = q.front().y;
			int found = q.front().found;
			if (map[x][y] == 2) {
				found = 1;
			}
			if (x == N - 1 && y == M - 1) {
				cout << t << "\n";
				return;
			}
			
			q.pop();
			for (int k = 0; k < 4; k++) {
				int nx = x + dx[k];
				int ny = y + dy[k];
				if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				if (visited[nx][ny][found]) continue;
				if (map[nx][ny] == 2 || (map[nx][ny] == 1 && found == 1) || map[nx][ny] == 0) {
					
					visited[nx][ny][found] = true;
					q.push({ nx,ny,found });
				}
			}
		}
		
	}
	
	cout << "Fail\n";
	
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> T;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	bfs();
	return 0;
}

  • 디버깅

    • 그람(검)을 찾은 경우 바로 found=1로 변환시켜 visited[x][y][0]이 check가 되지 않은 점을 꾸준함님의 풀이 를 통해 알게 되었습니다.

  • 제출결과

    0ms

3.마무리

  • 단순한 BFS문제였지만 아주 사소한 차이로 인해 풀이가 완벽하지 못했습니다.
 BOJ

Related Posts