글 읽기 - 두 코드의 차이점을 모르겠습니다

shyne2496 1년 전 0

첫번째 코드는 오답 코드

두번째 코드는 정답 코드입니다

두 코드의 논리 자체는 동일한데 왜 다른 결과가 나오는지 모르겠어서 질문드립니다.

//오답 코드
#include <iostream>
#include <cstring>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int T;
	char building[102][102];
	bool visited[102][102];
	bool keys[26]; // 사용가능한 열쇠
	int dy[4] = {-1, 1, 0, 0};
	int dx[4] = {0, 0, -1, 1};
	
	cin >> T;
	while(T--){
		memset(keys, false, sizeof(keys));
		memset(visited, false, sizeof(visited));
		
		queue<pair<int, int>> Q;
		vector<pair<int, int>> notOpened[26];
		
		int cnt = 0; // 훔친 문서 개수
		int h, w;
		cin >> h >> w;
		for(int i=1; i<h+1; i++){
			for(int j=1; j<w+1; j++){
				cin >> building[i][j];
				if(building[i][j] == '*'){
					visited[i][j] = true;
				}
			}
		}
		for(int i=1; i<h+1; i++){
			visited[i][0] = true;
			Q.push({i, 0});
			visited[i][w+1] = true;
			Q.push({i, w+1});
		}
		for(int j=1; j<w+1; j++){
			visited[0][j] = true;
			Q.push({0, j});
			visited[h+1][j] = true;
			Q.push({h+1, j});
		}
		string s;
		cin >> s;
		if(s != "0"){
			for(int i=0; i<s.size(); i++){
				keys[s[i]-'a'] = true;
			}
		}
		
		while(!Q.empty()){
			int y = Q.front().first;
			int x = Q.front().second;
			Q.pop();
			
			for(int i=0; i<4; i++){
				int ty = y+dy[i];
				int tx = x+dx[i];
				if(ty>-1 && ty<h+2 && tx>-1 && tx<w+2){
					char tmp = building[ty][tx];
					if(!visited[ty][tx]){
						if(tmp == '.'){
							visited[ty][tx] = true;
							Q.push({ty, tx});
						}
						else if(tmp == '$'){
							visited[ty][tx] = true;
							Q.push({ty, tx});
							cnt++;
						}
						else{
							if(tmp>='a' && tmp<='z'){
								visited[ty][tx] = true;
								Q.push({ty, tx});
								if(!keys[tmp-'a']){
									keys[tmp-'a'] = true;
									while(!notOpened[tmp-'a'].empty()){
										pair<int, int> T = notOpened[tmp-'a'].back();
										visited[T.first][T.second] = true;
										Q.push(T);
										notOpened[tmp-'a'].pop_back();
									}
								}
							}
							if(tmp>='A' && tmp<='Z'){
								if(keys[tmp-'A']){
									visited[ty][tx] = true;
									Q.push({ty, tx});
								}
								else{
									notOpened[tmp-'A'].push_back({ty, tx});
								}
							}
						}
					}
				}
			}
		}
		cout << cnt << "\n";
	}
	
	return 0;
}

//정답 코드
#include <iostream>
#include <queue>

using namespace std;

int h,w;
char map[105][105];
bool keys[26];
bool visited[105][105];

struct pos{
	int x,y;
	
	pos(int nx, int ny) : x(nx), y(ny) {}
};

void Search(){
	cin >> h >> w;
	
	for (int y = 0; y < h; y++){
		string s;
		cin >> s;
		for (int x = 0; x < w; x++){
			map[y+2][x+2] = s[x];
		}
	}
	
	h += 4;
	w += 4;
	
	for (int y = 0; y < h; y++){
		map[y][0] = map[y][w-1] = '*';
		map[y][1] = map[y][w-2] = '.';
	}
	for (int x = 1; x < w-1; x++){
		map[0][x] = map[h-1][x] = '*';
		map[1][x] = map[h-2][x] = '.';
	}
	
	string s;
	cin >> s;
	for (int i = 0; i < 26; i++)
		keys[i] = false;
	if (s != "0"){
		for (size_t i = 0; i < s.length(); i++){
			keys[s[i] - 'a'] = true;
		}
	}
	
	queue<pos> q;
	queue<pos> doorqs[26];
	q.push(pos(1,1));
	int cnt = 0;
	
	for (int y = 0; y < h; y++){
		for (int x = 0; x < w; x++){
			visited[y][x] = false;
		}
	}
	
	int ds[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
	while (!q.empty()){
		pos p = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++){
			int x = p.x + ds[i][0];
			int y = p.y + ds[i][1];
			int c = map[y][x];
			
			if (!visited[y][x]){
				visited[y][x] = true;
				if (c == '*'){
					continue;
				}
				
				if (c == '$'){
					cnt++;
				}
				else if ((c >= 'a') && (c <= 'z')){
					if (!keys[c - 'a']){
						keys[c - 'a'] = true;
						queue<pos> &doorq = doorqs[c - 'a'];
						while (!doorq.empty()){
							q.push(doorq.front());
							doorq.pop();
						}
					}
				}
				else if ((c >= 'A') && (c <= 'Z')){ 
					if (!keys[c - 'A']){
						doorqs[c - 'A'].push(pos(x,y));
						continue;
					}
				}
				
				q.push(pos(x,y));
			}
		}
	}
	cout << cnt << "\n";
}

int main(){
	int T;
	cin >> T;
	while (T--){
		Search();
	}
	return 0;
}

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

문제

문제

출처

ICPC

두 코드의 차이점을 모르겠습니다

shyne2496 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말