글 읽기 - 불 문제 질문입니다!

ekthadl40 4년 전 0

대회 테스트 케이스 모두 통과합니다.

질문게시판 보고 바로 탈출할 수 있는 경우, 불이 없는 경우 넣어봤는데 통과하지만 틀렸다고 뜹니다.

구현방식은, bfs를 할 때 불을 먼저 전파시켜서 입력 map을 업데이트합니다. 그 후에 사람이 이동할 수 있는 공간을 큐에 push하는 식으로 구현했습니다.

bfs 구현 방식에 문제가 있다면 알려주시면 감사하겠습니다!! 고수님들 부탁드려요!!

다른 질문들 보니 불 bfs와 사람 bfs를 따로 수행하던데, 왜 그렇게 하는지 모르겠습니다... 제가 동시에 수행시켰기 때문에 틀린걸까요? 그게 문제라면 따로 수행시켜야하는 이유가 뭔가요?

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int w, h;
char map[1002][1002];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
bool check[1002][1002];//사람위치 visit

typedef struct {
	int y = -1;
	int x = -1;
}POS;

int bfs(POS s, queue<POS> &f) {
	queue<POS> p;//사람위치 큐
    //f:불위치 큐
	int time = 0;
	p.push(s);
	check[s.y][s.x] = true;

	while (!p.empty()) {
		int p_s = p.size();
		int f_s = f.size();
        //불 확산
		while (f_s--) {
			POS cur_f = f.front();
			f.pop();
			for (int i = 0;i < 4;i++) {
				POS next_f = { cur_f.y + dy[i],cur_f.x + dx[i] };
				if (next_f.y < 0 || next_f.y >= h || next_f.x < 0 || next_f.x >= w) continue;
				if (map[next_f.y][next_f.x] == '*' || map[next_f.y][next_f.x] == '#') continue;
				map[next_f.y][next_f.x] = '*';
				f.push(next_f);
			}
		}
        //사람 이동
		while(p_s--){
			POS cur = p.front();
			p.pop();
			if (cur.y == 0 || cur.y == h - 1 || cur.x == 0 || cur.x == w - 1)return time+1;
			for (int i = 0;i < 4;i++) {
				POS next = { cur.y + dy[i],cur.x + dx[i] };
				if (next.y < 0 || next.y >= h || next.x < 0 || next.x >= w) continue;
				if (map[next.y][next.x] == '.' && !check[next.y][next.x]) {
					check[next.y][next.x] = true;
					p.push(next);
				}
			}
		}
		time++;
	}
	return -1;
}

int main(void)
{
	int test_case;
	//freopen("F.txt", "r", stdin);
	scanf("%d\n", &test_case);
	while(test_case--) {
		POS start;
		int answer = 0;
		queue<POS> fire;
		scanf("%d %d\n", &w, &h);
		for (int i = 0;i < h;i++) {
			memset(check[i], false, sizeof(check[i]));
			for (int j = 0;j <= w;j++) {
				scanf("%c", &map[i][j]);
				if (map[i][j] == '@') {
					start = { i,j };
					map[i][j] = '.';
				}
				else if (map[i][j] == '*') fire.push({ i,j });
			}
		}
		answer = bfs(start, fire);
		if (answer == -1)printf("IMPOSSIBLE\n");
		else printf("%d\n", answer);
	}
	return 0;
}

gumdung 4년 전 1

일단 고수는 아니지만 저도 조금이라도 도움될 만한 답변 받으면 너무 감사함을 느껴서 이렇게 답변을 남깁니다.

작성자님이 짜신 코드를 보면 44번 line 에서 현재 큐에서 뽑아낸 좌표가 맵을 벗어났을때 time을 return 시켜주도록 하셨는데

47번 line에서 이미 범위에 벗어난 좌표들은 continue로 걸러주고 계십니다.

답이 어떻게 도출 되는지는 모르겠는데 저부분을 고쳐주었더니 ac를 받았습니다.

또한 왜 불 bfs 와 사람 bfs를 따로하는지 궁금하다고 하셨는데

문제그대로 사람이 출구까지 최단거리로 이동하기 위해서 불이 번지는 걸 피해 이동해야 되기 때문입니다.(뭐라고 더 자세히 설명을 드려야 될지 모르겠군요.죄송합니다)

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int w, h;
char map[1002][1002];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
bool check[1002][1002];//사람위치 visit

typedef struct {
	int y = -1;
	int x = -1;
}POS;

int bfs(POS s, queue<POS>& f) {
	queue<POS> p;//사람위치 큐
	//f:불위치 큐
	int time = 0;
	p.push(s);
	check[s.y][s.x] = true;

	while (!p.empty()) {
		int p_s = p.size();
		int f_s = f.size();
		//불 확산
		while (f_s--) {
			POS cur_f = f.front();
			f.pop();
			for (int i = 0; i < 4; i++) {
				POS next_f = { cur_f.y + dy[i],cur_f.x + dx[i] };
				if (next_f.y < 0 || next_f.y >= h || next_f.x < 0 || next_f.x >= w) continue;
				if (map[next_f.y][next_f.x] == '*' || map[next_f.y][next_f.x] == '#') continue;
				map[next_f.y][next_f.x] = '*';
				f.push(next_f);
			}
		}
		//사람 이동
		while (p_s--) {
			POS cur = p.front();
			p.pop();
			
			for (int i = 0; i < 4; i++) {
				POS next = { cur.y + dy[i],cur.x + dx[i] };
				if (next.y < 0 || next.y >= h || next.x < 0 || next.x >= w) return time + 1;
				if (map[next.y][next.x] == '.' && !check[next.y][next.x]) {
					check[next.y][next.x] = true;
					p.push(next);
				}
			}
		}
		time++;
	}
	return -1;
}

int main(void)
{
	int test_case;
	//freopen("F.txt", "r", stdin);
	scanf("%d\n", &test_case);
	while (test_case--) {
		POS start;
		int answer = 0;
		queue<POS> fire;
		scanf("%d %d\n", &w, &h);
		for (int i = 0; i < h; i++) {
			memset(check[i], false, sizeof(check[i]));
			for (int j = 0; j <= w; j++) {
				scanf("%c", &map[i][j]);
				if (map[i][j] == '@') {
					start = { i,j };
					map[i][j] = '.';
				}
				else if (map[i][j] == '*') fire.push({ i,j });
			}
		}
		answer = bfs(start, fire);
		if (answer == -1)printf("IMPOSSIBLE\n");
		else printf("%d\n", answer);
	}
	return 0;
}

ekthadl40 4년 전 0

gumdung님, 너무 감사합니다!

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

문제

문제

출처

ICPC

불 문제 질문입니다!

ekthadl40 4년 전 0

gumdung 4년 전 1

ekthadl40 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말