글 읽기 - 로직 한번만 확인부탁드려요..

hssk1528 5년 전 0

bfs로 먼저 불이 번지는 순서를 계산하고

dfs로 미로 밖으로 나가는 경로 탐색하면서 최단경로를 계산하였는데요

게시판에 올려주신 사이트 들어가서 테스트케이스도 모두 확인해봤는데 다 맞게나옵니다ㅜㅜ

어디서 틀렸는지 봐주실수 있을까요..

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

int n, m;  // 행과 열의 개수
char map[1000][1000];  // 미로의 상태
int inmap[1000][1000];
int visited[1000][1000];
int res = 987654321;
queue< pair<int, int> > q;

const int mx[4] = { 0,0,1,-1 };
const int my[4] = { 1,-1,0,0 };

void fire() {

	while (!q.empty()) {
		pair<int, int> here = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			pair<int, int> there = make_pair(here.first + mx[dir], here.second + my[dir]);

			// 범위 벗어나면 넘어감
			if (there.first < 0 || there.first >= n || there.second < 0 || there.second >= m) continue;

			// 탐색하는 지점이 빈 공간이고 아직 불이 번지지않았으면
			if (map[there.first][there.second] == '.' && inmap[there.first][there.second] == -1) {
				// 불이 번지고, 큐에 넣어줌
				inmap[there.first][there.second] = inmap[here.first][here.second] + 1;
				q.push(there);
			}
		}
	}
}

void escape(pair<int, int> here, int sec) {
	// 현재 위치가 미로 밖이면 탈출 성공
	if (here.first < 0 || here.first >= n || here.second < 0 || here.second >= m) {
		res = min(res, sec);
		return;
	}

	// 현재 위치가 불이났거나 벽이면 종료
	if (map[here.first][here.second] == '#' || (inmap[here.first][here.second] != -1 &&
		inmap[here.first][here.second] <= sec)) return;

	// 이미 방문한 지점이면 종료
	if (visited[here.first][here.second] == 1) return;
	visited[here.first][here.second] = 1;

	// 동서남북 방향으로 이동
	for (int dir = 0; dir < 4; dir++) {
		pair<int, int> there = make_pair(here.first + mx[dir], here.second + my[dir]);
		escape(there, sec + 1);
	}
}

int main() {
	cin >> n >> m;
	int jx, jy;  // 최초 지훈이 위치의 x,y 좌표

	// inmap 배열 -1로 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			inmap[i][j] = -1;
		}
	}

	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;

		for (int j = 0; j < m; j++) {
			map[i][j] = input[j];
			if (map[i][j] == 'F') {
				q.push(make_pair(i, j));
				inmap[i][j] = 0;
			}
			if (map[i][j] == 'J') {
				jx = i;
				jy = j;
				map[i][j] = '.';
			}
		}
	}

	fire();
	escape(make_pair(jx, jy), 0);

	if (res == 987654321) cout << "IMPOSSIBLE" << endl;
	else cout << res << endl;
	return 0;
}

djm03178 5년 전 0

DFS로 하면 같은 위치를 나중에 방문할 때 거리가 갱신되어있을 수도 있는데 방문 체크 때문에 나아가지 못하고 돌아가게 됩니다.

7 6
######
#.J..#
#.##.#
#....#
..####
#.#...
#...#F

hssk1528 5년 전 0

답변감사합니다!!

dfs로 해결해보고 싶었는데 도저히 안돼서 bfs로 바꾸어서 정답받았습니다ㅜㅜ

djm03178 5년 전 2

원래 최단거리는 DFS로 하는 게 아닙니다. 지금과 같은 문제 때문에 거리가 갱신되면 방문 체크를 무시하고 다시 진행해야 한다는 점 때문에 처리가 까다로울 뿐 아니라 시간복잡도도 제곱에 가깝게 늘어날 수 있게 됩니다. 최단거리는 무조건 BFS입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

로직 한번만 확인부탁드려요..

hssk1528 5년 전 0

djm03178 5년 전 0

hssk1528 5년 전 0

djm03178 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말