글 읽기 - 로직 질문 드립니다.

blackbbean 5년 전 0

9328번 알고리즘 로직 질문드립니다.

대부분의 블로그 문제 풀이가,

탐색을하면서 문을 열고, 문을 열수 없다면 문 큐에 넣고, 열수 없었던 문의 열쇠를 찾으면

해당 문으로 이동하여, 탐색을 진행하는 로직으로 짜여있는걸 확인하였습니다.

하지만 , 저같은 경우는 문제 풀이를 할 때, 조금 다른 방향으로 접근 하였습니다.

visited 행렬을 따로 두고, visited 행렬에 보유한 key의 갯수값을 저장함으로써

방문 했음 여부를 나타내었고

이 문제의 주된 특징인 과거에 방문하였던 지점을 다시 방문해야할 경우를

이전에 방문했을 때보다 현재 방문할경우의 key의 갯수가 클때라 생각하여 (visited 값이 이전보다 클 경우)

이전에 방문했을 때보다 현재 방문할 경우의 key의 갯수가 클때만 해당 지점을 다시 방문할 수 있도록 하였습니다.

제 개인적인 생각으로는 전혀 문제될 것이 없는 로직인데 계속 '틀렸습니다'가 뜨는 이유를 잘 모르겠습니다 ㅠㅠ

실제 대회의 testcase를 돌려봤을 때, 대부분 정답 처리가 되었지만 몇몇 케이스의 경우가 정답보다 작은 값을 출력하는 경우가 존재하였습니다.

맵의 크기도 큰 편이라 디버깅 할 엄두도 안나네요 ㅠㅠ

유사한 문제라 생각하는

1194번 '달이 차오른다 가자' https://www.acmicpc.net/proble...

역시 이런 방식으로 풀었고 역시 오답 처리가 되어서 왜 이 풀이가 되지 않는지 궁금해졌습니다.

그럼 답변 기다리겠습니다 !!

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <string.h>
using namespace std;
typedef struct {
	int row;
	int col;
}POS;
int H, W;
int tc;
char map[103][103];
bool key[27] = { false, }; //이렇게 놓을수있는 이유는 path를 구하는것이 아니기 때문에 ..
int visited[103][103];
int initKey;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int answerCount;
vector<int> answer;
void bfs() {
	queue<POS> q;
	q.push({ 0,0 });
	visited[0][0] = initKey;
	while (!q.empty()){
		POS qd = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = qd.row + dx[i];
			int nc = qd.col + dy[i];
			if (nr<0 || nr>H + 1 || nc<0 || nc>W + 1||map[nr][nc]=='*')
				continue;
			if (visited[nr][nc] == -1) {//방문한 적 없을때 
				if (map[nr][nc] == '.') {
					q.push({ nr,nc });
					visited[nr][nc] = visited[qd.row][qd.col]; //key값이 변화 되지 않으니 그대로
				}
				else if (map[nr][nc] >= 'a' && map[nr][nc] <= 'z') {
					key[map[nr][nc] - 'a'] = true;
                    //key가 추가되니 +1
					visited[nr][nc] = visited[qd.row][qd.col] + 1;
					q.push({ nr,nc });
				}
				else if (map[nr][nc] >= 'A'&& map[nr][nc] <= 'Z' && key[map[nr][nc] - 'A']) {
					visited[nr][nc] = visited[qd.row][qd.col];//key값이 변화 되지 않으니 그대로
					q.push({ nr,nc });
				}
				else if (map[nr][nc] == '$') {
					q.push({ nr,nc });
					visited[nr][nc] = visited[qd.row][qd.col];//key값이 변화 되지 않으니 그대로
					answerCount++;
				}
			}
			else { //예전에 방문한 적이 있을 경우 
				if (visited[nr][nc] < visited[qd.row][qd.col]) { //보유 key갯수가 달라졌을 경우 
					visited[nr][nc] = visited[qd.row][qd.col];
					q.push({ nr,nc });
				}

			}
		}
	}
}
int main() {
	scanf("%d", &tc);
	for (int tcval = 0; tcval < tc; tcval++) {
		answerCount = 0;
		initKey = 0;
		memset(key, false, sizeof(key));
		memset(visited, -1, sizeof(visited));
		memset(map, '\0', sizeof(map));
		scanf("%d %d", &H, &W);
		string inpath;
		for (int i = 1; i <= H; i++) {
			cin >> inpath;
			for (int j = 1; j <= W; j++) {
				map[i][j] = inpath[j - 1];
			}
		}

        //보유 key 갯수 count, key배열에 상태 저장 
		string input;
		cin >> input;
		if (input[0] != '0') {
			for (int j = 0; j < input.size(); j++) {
				key[input[j] - 'a'] = true;
				initKey++;
			}
		}
        
        // 겉 테두리 '.' 놓기
		for (int i = 0; i <= W+1; i++) {
			map[0][i] = '.';
			map[H + 1][i] = '.';
		}
		for (int i = 0; i <= H + 1; i++) {
			map[i][0] = '.';
			map[i][W + 1] = '.';
		}
		bfs();
		printf("%d\n", answerCount);
    }
}