글 읽기 - 9328. 질문있습니다. 살려주세요 help!!!!!!!!

minjae200 5년 전 0

우선모든 TC다 통과하고 어디가 잘못되서 틀렸다고 나오는지 모르겠습니다.

아이디어 : (0,0)에서 시작해서 우선 BFS탐색을 시도합니다.

원래 기존에 가지고있던 key를 사용하여 문을 열수있으면 열고 가는식으로 진행하였습니다.

BFS를 마치면 그 과정에서 새롭게 얻은 key를 가지고 다시 door에 저장되어있던 door의 좌표를 통하여

BFS를 시도합니다. 이과정에서 새롭게 key를 주운것이 없으면 더이상 door를 열고 들어갈수없다고

판단하여 while문을 빠져나왔습니다. ( 이역할을 keyflag가 해줍니다.)

무엇이 문제일까요

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

int h, w, result;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
char map[102][102];
bool visited[102][102];
bool key[27], keyflag;
vector<pair<int, int>> door;

bool CheckRange(int y, int x)
{
	if (0 <= y && y <= h+1  && 0 <= x && x <= w+1 ) return true;
	else return false;
}

void BFS(int y, int x)
{
	//단순 BFS 알고리즘
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));
	visited[y][x] = true;

	while (!q.empty()) {
		int curX = q.front().second;
		int curY = q.front().first;
		q.pop();

		if (map[curY][curX] == '$')
			result++;

		for (int i = 0; i < 4; i++) {
			int next_x = curX + dx[i];
			int next_y = curY + dy[i];
			if (!CheckRange(next_y, next_x)) continue;
			if (visited[next_y][next_x]) continue;
			if (map[next_y][next_x] == '*') continue;

			if ('A' <= map[next_y][next_x] && map[next_y][next_x] <= 'Z') {
				if (key[map[next_y][next_x] - 'A']) {
					q.push(make_pair(next_y, next_x));
					visited[next_y][next_x] = true;
				}
			}
			else if (map[next_y][next_x] == '.' || map[next_y][next_x] == '$') {
				q.push(make_pair(next_y, next_x));
				visited[next_y][next_x] = true;
			}
			else if ('a' <= map[next_y][next_x] && map[next_y][next_x] <= 'z') {
				key[map[next_y][next_x] - 'a'] = true;
				visited[next_y][next_x] = true;
				keyflag = true;
			}
		}
	}
}

int main(void)
{
	int T; cin >> T;
	while (T--) {
		// 전역변수 초기화 (테스트케이스가 여러개여서)
		for (int i = 0; i < 102; i++) {
			for (int j = 0; j < 102; j++) {
				map[i][j] = '.';
			}
		}
		memset(visited, false, sizeof(visited));
		memset(key, false, sizeof(key));
		result = 0;
		door.clear();

		//map[i][j]가 문이면 door에 push
		cin >> h >> w;
		for (int i = 1; i <= h; i++) {
			for (int j = 1; j <= w; j++) {
				cin >> map[i][j];
				if ('A' <= map[i][j] && map[i][j] <= 'Z')
					door.push_back(make_pair(i, j));
			}
		}

		// 보유중인 키 입력받고 저장
		string HaveKey; cin>>HaveKey;
		if (HaveKey.compare("0")) {
			for (int i = 0; i < HaveKey.length(); i++) {
				key[HaveKey[i] - 'a'] = true;
			}
		}
		//시작은 (0,0)에서 BFS로 탐색
		BFS(0, 0);
		// 탐색을 끝마치고 열쇠를 주웠으면 door 체크
		// 못주웠으면 while문 break;
		keyflag = true;
		while (keyflag) {
			keyflag = false;
			for (int i = 0; i < door.size(); i++) {
				int door_x = door[i].second;
				int door_y = door[i].first;
				if (!visited[door_y][door_x] && key[map[door_y][door_x] - 'A']) {
					BFS(door_y, door_x);
				}
			}
		}
		cout << result << endl;
	}
	return 0;
}

djm03178 5년 전 1

우선 CheckRange 함수의 범위가 이상합니다. 좌표는 세로 1에서 h, 가로 1에서 w까지만 존재하는데 왜 0과 h+1, 0과 w+1을 각각 허용하고 있나요?

그리고 열쇠를 가지고 있다고 해서 해당 문에 반드시 도달할 수 있는 건 아닙니다. 밖에서부터 안으로 들어오는 경로가 있어야 합니다.

1
3 4
****
*$A*
****
a

minjae200 5년 전 0

감사합니다 밖에서 안으로 들어오는 경로를 체크안하고 그냥 문의 위치부터 BFS를 써서 생기는 문제였네요

checkRange는 이렇게 생각했습니다. 어느지점에서 시작할지 애매해서

세로 1~h 가로 1~w까지 입력받고

그 테두리도 '.'로 설정하여

BFS를 시도하는식으로 했습니다.

! ! ! ! ! !
!* * * * !
!* $ A *!
!* * * * !
! ! ! ! ! ! -> 이런식으로

두번째로 언급하신 문제때문이였습니다. 감사합니다.

minjae200 5년 전 0

map을 입력받을때 door를 push하는게 아니라

BFS에서 'A'~'Z' 만날때 door에 push하였고

'a'~'z' 열쇠 얻는 부분에서 큐에 좌표를 push안해줬었네요

AC받았습니다. 도움 감사합니다.

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

문제

문제

출처

ICPC

9328. 질문있습니다. 살려주세요 help!!!!!!!!

minjae200 5년 전 0

djm03178 5년 전 1

minjae200 5년 전 0

minjae200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말