글 읽기 - DFS로 풀지않았는데요...

minripex 3년 전 0

팩맨 게임처럼 1이 입력된 좌표를 오름차순(배열순서대로)으로 검사하며 오른쪽과 아래에 1이있으면 그 좌표는 값을 0으로 바꿔주는 식으로 풀었습니다

땅따먹기처럼 하다보면 결국 지역마다 1이 하나만 남게됨으로

마지막에 1이 몇개 있는지 구해서 답이 나오게했어요

게시글에 있는 반례도 넣어봤지만 문제가 안찾아지네요

혹시 틀린부분이 있을까요 아니면 접근이 틀렸을까요

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int T;
	cin>>T;
	int M,N,K;
	int cnt=0;
	vector<int> cntarr;
	for(int i=0;i<T;++i)
	{
		vector<pair<int,int>> arr; //1이 입력된 좌표
		cin>>M>>N>>K;
		vector<vector<int>> v(M,vector<int>(N,0));

		for(int j=0;j<K;++j)
		{
			int x;
			int y;
			cin>>x>>y;
			v[x][y]=1;
		}

		for(int i=0;i<M;++i)
		{
			for(int j=0;j<N;++j)
			{
				if(v[i][j]==1)
				{
					arr.push_back(make_pair(i,j)); //1이 입력된 좌표를 차례대로 저장
				}
			}
		}
//		
//		for(int i=0;i<K;++i)
//		{
//			cout<<arr[i].first<<" "<<arr[i].second<<endl;
//		}
		for(int k=0;k<K;++k)
		{
			int x=arr[k].first;
			int y=arr[k].second;
			if(x==M-1&&y!=N-1) //맨 아랫줄일때는 오른쪽 칸만 검사
			{
				if(v[x][y+1]==1)
				{
					v[x][y]=0;
				 } 
			}
			else if(y==N-1&&x!=M-1) //맨 오른쪽줄일때는 아래칸만 검사
			{
				if(v[x+1][y]==1)
				{
					v[x][y]=0;
				}
			}
			else if(x==M-1&&y==N-1) //맨 마지막칸일때는 검사 안함
			{}
			else                     //오른쪽과 아래칸만 검사
			{
				if(v[x][y+1]==1||v[x+1][y]==1)
				{
					v[x][y]=0;
				}
			}
		}
		cnt=0;
		for(int i=0;i<K;++i)    //1이 입력된 좌표를 돌아다니며 1의 갯수 구함
		{
			int x=arr[i].first;
			int y=arr[i].second;
			if(v[x][y]==1)
			{
				cnt++;
			}
		}
		cntarr.push_back(cnt);
//      for(int i=0;i<M;++i)
//		{
//			for(int j=0;j<N;++j)
//			{
//				cout<<v[i][j]<<" ";
//			}
//			cout<<endl;
//		}
	}
	for(int i=0;i<T;++i)
	{
		cout<<cntarr[i]<<endl;
	}
	
}

djm03178 3년 전 1

반례입니다.

1
2 3 5
0 0
1 0
0 1
1 2
0 2

정답: 1
이 코드의 출력: 2

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

문제

문제

출처

ICPC

DFS로 풀지않았는데요...

minripex 3년 전 0

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말