글 읽기 - bfs로 했는데 메모리 초과가 납니다..

seungwonoh57 6년 전 0

visited를 걸러줘야 하는 것 같은데 어떻게 해야 될지 모르겠습니다. 도와주세요 ㅠㅠ

#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];


typedef struct coordinates{
	int x;
	int y;
}Coordinate;

void bfs() {
	queue <pair<Coordinate, set<char>>> q;
	set <char> list;
	Coordinate cur;
	
	list.insert(adj[0][0]);
	cur.x = 0;
	cur.y = 0;
	
	q.push(make_pair(cur, list));
	visit.insert(make_pair(cur, list));
	
	while (!q.empty()) {
		cur = q.front().first;
		list = q.front().second;
		q.pop();
		
		if(ans < list.size()){
			ans = list.size();
		}
		
		for(int k = 0 ; k < 4; k++){
			Coordinate next;
			set <char> next_list = list;
			
			next.x = cur.x + dx[k];
			next.y = cur.y + dy[k];
			
			if(next.x >= 0 && next.x < R && next.y >= 0 && next.y < C){
				
				if(!list.count(adj[next.x][next.y])){
					next_list.insert(adj[next.x][next.y]);
					q.push(make_pair(next, next_list));
						
                }
					
            }
			
		}
	}
   
}


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);
		}
	}
	
	bfs();
	
	cout << ans << endl;
	
	return 0;
}

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

문제

문제

출처

ICPC

bfs로 했는데 메모리 초과가 납니다..

seungwonoh57 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말