인프런 커뮤니티 질문&답변

http://boj.kr/972b9dbcb4b24d56a34b37744dde4aec

원래 fire마다 순차적으로 bfs를 돌리는 것이 목표였습니다. 순차적으로 bfs를 진행하면서

이전의 불들이 현재 위치까지 걸리는 시간(visited에 계속 기록)보다

현재 돌리는 fire가 현재 위치에 도달하는 시간이 더 적을 경우

그 적은 시간을 갱신하는 식으로 visited를 완성해나가고자 했습니다.

그 후 지훈이가 이동하는 거리를 visited2에 기록한 후 벡터에 넣어놨던 탈출 위치를

반복문을 통해 돌면서 지훈 이동 거리(visited2)가 불 거리(visited)보다 작을 경우

지훈이가 해당 탈출 위치에 더 빨리 도착한다는 것이므로 그 거리들을 벡터에 넣어놓고

정렬하여 가장 작은 거리를 마지막에 출력하고자 했습니다.

이전 시도했던 코드는 bfs 함수에서 if (visited[ny][nx] > visited[y][x]) 이 부분 때문에

계속 큐 사이즈가 올라 갔습니다. 어쩌피 ny, nx는 현재 위치에서 상하좌우 한 칸씩 이동한 곳이기 때문에 그 차이가 한 칸이라면 탐색할 이유가 없어서(같은 거리이므로) if (visited[ny][nx] > visited[y][x] + 1)로 조건을 고쳤습니다.(위 링크)

근데 이렇게 수정하니 메모리 초과는 안뜨지만 여전히 에러가 나옵니다.

어떤 반례가 있는 걸까요....?

안녕하세요 ㅎㅎ

원래 fire마다 순차적으로 bfs를 돌리는 것이 목표였습니다. 순차적으로 bfs를 진행하면서

이전의 불들이 현재 위치까지 걸리는 시간(visited에 계속 기록)보다

현재 돌리는 fire가 현재 위치에 도달하는 시간이 더 적을 경우

그 적은 시간을 갱신하는 식으로 visited를 완성해나가고자 했습니다.

>> 해당 로직은 이해했는데요. ㅎㅎ 근데 사실 그러한 로직은 비효율적입니다.

			if (ny < r && ny >= 0 && nx < c && nx >= 0 && m[ny][nx] != '#') {
				if (visited[ny][nx] > visited[y][x] + 1) {

bfs는 방문한 정점은 다시 방문하지 않는다. 라는 특징을 가지고 해당 부분 때문에 빠릅니다. 근데 이 코드는 방문한 정점을 다시 방문하게 되죠.

즉, 비효율적이게 됩니다.

이를 queue에다가 시작 F정점들을 담아두고 단한번만 bfs를 돌리게 수정하는게 좋습니다.

어떤 반례가 있는 걸까요....?

>> 반례는 몇개 시도해봤는데 잘 안나오네요...

찾는대로 답변 드리겠습니다.

감사합니다.

반례 찾았습니다. ㅎㅎ

예를 들어
FF..

이렇게 되어있을 때

오른쪽 F부터 bfs가 시작되면

2123

이렇게 visited배열이 완성되겠죠?

근데 여기서

왼쪽 F이 시작되면

1234

이렇게 되어버리지 않을까요?

원래는 이게 맞을 거 같습니다.

1123

감사합니다.

항상 빠른 답변 감사합니다!

2123 상태에서 왼쪽 F가 시작되면 bfs를 호출해서 우선 1123이 될테고(while문 이전 초기화)

while문에 들어가면 if (visited[ny][nx] > visited[y][x] + 1) 조건을 만족시키지 못하기 때문에

더이상 큐에 push가 되지 않고 1123이 그대로 유지될 것 같은데요...?

실제로 돌려보면 0012로 출력됩니다.(전 시작할 때 0으로 지정해서 1씩 빠진 값으로 출력됩니다)

더이상 큐에 push가 되지 않고 1123이 그대로 유지될 것 같은데요...?

>> 네 그러네요..ㅜㅜ...이게 최솟값으로 갱신되서 그러는거 같습니다.

하하 하지만 반례를 찾았습니다.

3 3

.FF

..J

...

답 : 1

수강생님 코드 : 2

감사합니다.

else if를 잘못 설정해서 지훈이가 탈출 지역에 있을 때

탈출점을 push_back할 때 누락되는 부분이 있었군요

해당 부분을 아래와 같이 고쳤습니다.

for (int i = 0; i < r; i++) {

for (int j = 0; j < c; j++) {

cin >> m[i][j];

if (m[i][j] == 'J') pos = { i,j };

else if (m[i][j] == 'F') fire.push_back({ i, j });

if (i == r - 1 || j == c - 1 || i == 0 || j == 0) {

if (m[i][j] != '#') {

esc.push_back({ i,j });

}

}

}

}

드디어! 를 외치며 제출을 했는데 어림도 없었습니다....

이전과 같이 계속 2%에서 틀렸습니다 가 나오네요 ㅠㅠ

사실 강의보고 해당 알고리즘 대로 코드 구성해서 이미 해결한 문제이긴 한데

처음 생각했던 알고리즘도 말이 된다 싶어서 계속 시도해보고 있어요...

계속 반례가 나오는데 그만 놓아주어야 할까요...?

넴.. 놓아주어야 할 것 같습니다.

사실 저도 여러번 시도를 하고 있는데요.

이상하게 안되네요..

제가 qn님 코드 수정한 부분은 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
int r, c, cnt;
char m[1004][1004];
int visited[1004][1004];
int visited2[1004][1004];
vector<pair<int, int>> fire;
vector<pair<int, int>> esc;
vector<int> ret;

void bfs2(int y, int x) {
	visited2[y][x] = 0;
	queue<pair<int, int>> q;
	q.push({ y, x });

	while (q.size()) {
		tie(y, x) = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < r && ny >= 0 && nx < c && nx >= 0 && m[ny][nx] != '#' && visited2[ny][nx] == -1) {
				visited2[ny][nx] = visited2[y][x] + 1;
				q.push({ ny, nx });
			}
		}
	}

}

void bfs() {
	int y, x;
	queue<pair<int, int>> q;
	for (auto a : fire) {
		tie(y, x) = a;
		visited[y][x] = 0; 
		q.push({ y, x }); 
	} 
	while (q.size()) {
		tie(y, x) = q.front(); q.pop(); 
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < r && ny >= 0 && nx < c && nx >= 0 && m[ny][nx] != '#' && visited[ny][nx] == 2e9) { 
					visited[ny][nx] = visited[y][x] + 1;
					q.push({ ny, nx });
			} 
		}

		//cout << q.size() << "\n";
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	fill(&visited[0][0], &visited[0][0] + 1004 * 1004, 2e9);
	fill(&visited2[0][0], &visited2[0][0] + 1004 * 1004, -1);
	cin >> r >> c;

	pair<int, int> pos;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> m[i][j];
			if (m[i][j] == 'J') pos = { i,j };
			else if (m[i][j] == 'F') fire.push_back({ i, j });
			else if (i == r - 1 || j == c - 1 || i == 0 || j == 0) {
				if (m[i][j] != '#') {
					esc.push_back({ i,j });
				}
			}
		}
	}
	bfs();

	bfs2(pos.first, pos.second);

	for (auto a : esc) {
		if (visited2[a.first][a.second] < visited[a.first][a.second]) {
			ret.push_back(visited2[a.first][a.second] + 1);
		}
	}
	if (ret.size() == 0) {
		cout << "IMPOSSIBLE";
	}
	else {
		sort(ret.begin(), ret.end());
		cout << ret.front();
	}

	//cout << '\n';
	//for (int i = 0; i < r; i++) {
	//	for (int j = 0; j < c; j++) {
	//		cout << visited[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}

	//for (int i = 0; i < r; i++) {
	//	for (int j = 0; j < c; j++) {
	//		cout << visited2[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}

	return 0;
}

해결했습니다.

3 3

..F

.J#

.#.

이런 경우에서 [2][2]에 해당하는 자리가

visited2에서 -1(기본값 fill)로 초기화 된 후 방문 되지 않기 때문에

if (visited2[a.first][a.second] < visited[a.first][a.second]) (visited2 = 지훈, visited = 불)

이 조건문에 무조건 성립되어 ret 벡터에 -1에서 1을 더한 0 값이 들어가서

ret 벡터를 sort 후 답(벡터의 front())을 출력하면 0이 출력되는 문제가 있었습니다.

많은 답변 정말 감사합니다!!!

해결하셨다니 다행이네요.. ㅎㅎ

도움이 되어드리지 못한 것 같아 죄송한 마음 뿐입니다..

감사합니다.