글 읽기 - 한코드는 통과, 한코드는 37%틀리는데 두 코드의 차이를 모르겠습니다.

ktjs7252 2년 전 0

나머지 부분은 같고 벽세우는 코드만 다릅니다!!

//통과한 코드
	for(int i=0;i<v.size();i++)
	{
		for(int j=0;j<i;j++)
		{
			for(int k=0;k<j;k++)
			{
				arr[v[i].first][v[i].second]=arr[v[j].first][v[j].second]=arr[v[k].first][v[k].second]=1;
				solve();
				arr[v[i].first][v[i].second]=arr[v[j].first][v[j].second]=arr[v[k].first][v[k].second]=0;
			}
		}
	}

// 틀린코드
for(int i=0;i<v.size()-2;i++)
	{
		for(int j=i;j<v.size()-1;j++)
		{
			for(int k=j;k<v.size();k++)
			{
				arr[v[i].first][v[i].second]=arr[v[j].first][v[j].second]=arr[v[k].first][v[k].second]=1;
				solve();	
				arr[v[i].first][v[i].second]=arr[v[j].first][v[j].second]=arr[v[k].first][v[k].second]=0;
			}
		}
	}



//원본
#include<bits/stdc++.h>

using namespace std;

int n,m;
int arr[9][9];
int tmp[9][9];
int visited[9][9];
vector<pair<int,int>> v;
int answer;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void dfs(int x,int y)
{
	tmp[x][y]=-1;
	
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		
		if(nx>=0 && nx<n && ny>=0 && ny<m)
		{
			if(tmp[nx][ny]==0)
			{
				dfs(nx,ny);
			}
		}
	}
	
}

void solve()
{
	int kk=0;
	memset(tmp,0,sizeof(tmp));
	memset(visited,0,sizeof(visited));
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			tmp[i][j]=arr[i][j];
		}
	}
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(tmp[i][j]==2)
			{
				dfs(i,j);
			}
		}
	}
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(tmp[i][j]==0)
			{
				kk++;
			}
		}
	}
	answer=max(answer,kk);
}

int main()
{
	cin>>n>>m;
	
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>arr[i][j];
			if(arr[i][j]==0)
			{
				v.push_back({i,j});
			}
		}
	}
	
	for(int i=0;i<v.size();i++)
	{
		for(int j=0;j<i;j++)
		{
			for(int k=0;k<j;k++)
			{
				arr[v[i].first][v[i].second]=arr[v[j].first][v[j].second]=arr[v[k].first][v[k].second]=1;
				solve();
				arr[v[i].first][v[i].second]=arr[v[j].first][v[j].second]=arr[v[k].first][v[k].second]=0;
			}
		}
	}
	cout<<answer;
	
	return 0;
}

johan1103 2년 전 1

틀린 코드의 3중 for문에서는 i,j,k 셋 중에 둘 이상이 같은 값을 가질 수 있어서 벽을 한 개 또는 두 개만 설치하는 경우도 고려하기 때문에 틀리는 것 같습니다.

예를 들면 바이러스를 제외한 빈 공간이 3군데만 있는 경우에는 답이 0인데, 벽을 한 개 또는 두 개만 설치하면 답이 0보다 크게 나올 수 있습니다

ktjs7252 2년 전 0

감사합니다 ㅜㅜ

해결했습니다

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

문제

문제

출처

ICPC

한코드는 통과, 한코드는 37%틀리는데 두 코드의 차이를 모르겠습니다.

ktjs7252 2년 전 0

johan1103 2년 전 1

ktjs7252 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말