글 읽기 - 14502 연구소 문제 종료가 안되는데 어디가 잘못된걸까요?

dlswlfl 6년 전 0

코드에 문제가 없는것 같은데 어디가 잘못된 걸까요? ㅠㅠ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

int N, M;
int maximum=0;
int visited[10][10];
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

int bfs(int r,int c, int map[10][10]) {
	queue<pair<int, int> >q;
	visited[r][c] = 1;
	q.push({ r,c });

	int res=0;
	int a, b;

	while (!q.empty()) {
		res++;
		a = q.front().first, b = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			if (0 <= a + dr[i] && a + dr[i] < N && 0 <= b + dc[i] && b + dc[i] < M) {
				if (map[a + dr[i]][b + dc[i]]) continue;				
				if (visited[a + dr[i]][b + dc[i]])continue;
				visited[a + dr[i]][b + dc[i]] = 1;
				q.push({ a + dr[i],b + dc[i] });				
			}
		}
	}
	return res;
}

void dfs(int turn,int map[10][10]) {

	int res = 0;

	if (turn == 3) {
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 2 && visited[i][j] == 0) res += bfs(i, j,map);
				if (map[i][j] == 1) res++;
			}
		maximum = max(maximum, N*M - res);
	}

	for (int i = 0; i < N; i++) 
		for (int j = 0; j < M; j++) 
			if (map[i][j] == 0) {
				map[i][j] = 1;
				dfs(turn + 1,map);
				map[i][j] = 0;
			}
}

int main() {
	cin >> N >> M;
	int map[10][10];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> map[i][j];
	dfs(0,map);
	cout << maximum << '\n';
}

dldudwo10 6년 전 0

dfs함수에서 멈춰지지지가 않습니다.

void dfs(int turn,int map[10][10]) {

	int res = 0;

	if (turn == 3) {
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 2 && visited[i][j] == 0) res += bfs(i, j,map);
				if (map[i][j] == 1) res++;
			}
		maximum = max(maximum, N*M - res);
	}else{
        for (int i = 0; i < N; i++) 
		for (int j = 0; j < M; j++) 
			if (map[i][j] == 0) {
				map[i][j] = 1;
				dfs(turn + 1,map);
				map[i][j] = 0;
			}
    }
}

dldudwo10 6년 전 0

위처럼 else 넣어주시거나 아니면 if문에서 마지막에 return; 해주세요

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

문제

문제

출처

ICPC

14502 연구소 문제 종료가 안되는데 어디가 잘못된걸까요?

dlswlfl 6년 전 0

dldudwo10 6년 전 0

dldudwo10 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말