글 읽기 - 왜 check배열 대신 set으로 관리하면 안되는 걸까요!

seungwonoh57 6년 전 0

코드를 2개로 거의 비슷하게 짰는데

하나는 현재까지 밟은 알파벳들을 set에 넣어서

set size로 칸수를 세는 방법으로 최대 칸을 구했는데

틀렸다고 나옵니다.

반면 check 배열을 써서 알파벳을 구하면 됩니다.

왜 그런지 알고 싶습니다 ㅠㅠ

/* 안되는 코드 */
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <queue>
using namespace std;

int R, C;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1 , 1};
unsigned long ans = 0;
char adj[21][21];
set <char> list;
void dfs(int i, int j) {
	
	if(ans < list.size()){
		ans = list.size();
	}
		
	for(int k = 0 ; k < 4; k++){
		int x = i + dx[k];
		int y = j + dy[k];
			
			if(x >= 0 && x < R && y >= 0 && y < C){
				if(!list.count(adj[x][y])){
					list.insert(adj[x][y]);
					dfs(x, y);
				}
			}
    }
    list.erase(adj[i][j]);
    
}


int main(){
	string s1;
	set <char> list;
	scanf("%d %d", &R, &C);
	
	for(int i = 0; i < R; i++){
		cin >> s1;
		for(int j = 0; j < C; j++){
			adj[i][j] = s1.at(j);
		}
	}
	list.insert(adj[0][0]);
	dfs(0, 0);
	
	cout << ans << endl;
	
	return 0;
}

/* 되는 코드 */
#include <iostream>
#include <string>

using namespace std;

int R, C;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1 , 1};
int ans = 0;
char adj[21][21];
int check[26];

void dfs(int i, int j, int cnt) {

	if(ans < cnt){
		ans = cnt;
	}

	for(int k = 0 ; k < 4; k++){
		int x = i + dx[k];
		int y = j + dy[k];
			
		if(x >= 0 && x < R && y >= 0 && y < C){
			if(check[adj[x][y] - 'A'] == 0){
				check[adj[x][y] - 'A'] = 1;
				dfs(x, y, cnt+1);
			}
		}
	}
	
	check[adj[i][j] - 'A'] = 0;
}



int main(){
	string s1;
	scanf("%d %d", &R, &C);
	
	for(int i = 0; i < R; i++){
		cin >> s1;
		for(int j = 0; j < C; j++){
			adj[i][j] = s1.at(j);
		}
	}
	check[adj[0][0] - 'A'] = 1;
	dfs(0, 0, 1);
	
	cout << ans << endl;
	
	return 0;
}

practice1 3년 전 0

안되는 코드 39번 줄에 보면, set을 지역변수로 더 선언하고 계세요.

그래서 원래 의도하신대로 지우고 하면, 시간초과가 뜨는데요.
아무래도 기본 배열보다 속도 측면에서 느리다보니깐 발생하지 않나 싶습니다.

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

문제

문제

출처

ICPC

왜 check배열 대신 set으로 관리하면 안되는 걸까요!

seungwonoh57 6년 전 0

practice1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말