*먼저 문제를 보자*
문항 레벨은 골드 5로 비교적 높은 편이며 정답률은 약 56%이다.
호스트가 문제를 확인하면 일반적인 DFS 문제 그게 다라고 생각했습니다.
바로 코드를 살펴보겠습니다(전체 코드는 아래 참조).
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int dir_x(4){-1,0,1,0};
int dir_y(4){0,1,0,-1};
int map_noraml(101)(101){0};
int map_dif(101)(101){0};// 1: R / 2: G / 3: B
int visited(101)(101){0};
int n,color=0,cnt1=0,cnt2=0;
void dfs1(int x,int y){
color=map_noraml(x)(y);
visited(x)(y)=1;
for(int i=0;i<4;i++){
int dx=x+dir_x(i);
int dy=y+dir_y(i);
if(dx<0 || dx>n || dy<0 || dy>n)continue;
if(map_noraml(dx)(dy)==color && !visited(dx)(dy)){
dfs1(dx,dy);
}
}
}
void dfs2(int x,int y){
color=map_dif(x)(y);
visited(x)(y)=1;
for(int i=0;i<4;i++){
int dx=x+dir_x(i);
int dy=y+dir_y(i);
if(dx<0 || dx>n || dy<0 || dy>n)continue;
if(map_dif(dx)(dy)==color && !visited(dx)(dy)){
dfs2(dx,dy);
}
}
}
int main(){
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
char tmp;
cin>>tmp;
if(tmp=='R'){map_noraml(i)(j)=1; map_dif(i)(j)=1;}
else if(tmp=='G'){map_noraml(i)(j)=2; map_dif(i)(j)=1;}
else if(tmp=='B'){map_noraml(i)(j)=3; map_dif(i)(j)=2;}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!visited(i)(j)){
cnt1++;
dfs1(i,j);
}
}
}
memset(visited,0,sizeof(visited));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!visited(i)(j)){
cnt2++;
dfs2(i,j);
}
}
}
cout<<cnt1<<' '<<cnt2;
return 0;
}memset 사용 시 참고 사항 string.h 또는 memory.h 도서관
포함되지 않은 경우 백준 채점 시 컴파일 오류가 발생합니다.
-기여 결과-
