https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
이 문제는 2667번과 거의 동일하다.
다른 점이라면 테스트 케이스를 입력 받은만큼 실행한다는 것과, 배추가 있는 좌표를 찍어야 한다는 점 정도이다.
나머지는 2667번과 동일하게 DFS,BFS 모두로 풀 수 있을 것이다.
풀이 방법은 먼저 테스트 케이스를 몇 개 실행할지 입력 받는다. 그 다음에 가로 길이 M과 세로 길이 N을 입력 받고 배추의 갯수인 K를 입력받는다. 그 다음 아래 K개의 줄에 배추가 있는 좌표를 찍는다.
그런 후에 이제 밭 전체를 지나면서 배추가 있는 지점에서 탐색을 수행하는 일을 반복하여 배추가 인접한 곳의 갯수를 계산한다.
그래서 main메서드를 구현하면 아래와 같은 반복문 구조가 나온다.
for(int i=0; i<caseN; i++){
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
Graph g = new Graph(M,N);
for(int j=0; j<K; j++){
st=new StringTokenizer(br.readLine());
int x= Integer.parseInt(st.nextToken());
int y= Integer.parseInt(st.nextToken());
g.addEdge(x,y);
}
int num=0;
for(int j=0; j<N; j++){
for(int k=0; k<M; k++){
if(g.table[j][k]==1){
g.dfs(k,j);
num++;
}
}
}
sb.append(num).append("\n");
}
System.out.println(sb);
}그리고 이제 여기서 사용한 객체인 Graph의 클래스에서 DFS방식으로 탐색 과정을 구현하면, 아래의 코드처럼 재귀함수로 구현된다.
여기서 사용한 for문은 선택한 좌표의 상하좌우에 접근하여 배추가 있는지의 유무를 탐색하기위한 부분이다.
public void dfs(int Rx, int Ry){
if(table[Ry][Rx]==0){
return;
}
table[Ry][Rx]=0;
for(int i=0; i<4; i++){
int x = Rx+dx[i];
int y = Ry+dy[i];
if(x>=0 && y>=0 && x<M && y<N && table[y][x]==1){
dfs(x,y);
}
}
}
Graph클래스 전체는 아래와 같다.
class Graph{
int N;
int M;
int[][] table;
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};
public Graph(int M, int N){
table=new int[N][M];
this.N=N;
this.M=M;
}
public void addEdge(int x, int y){
table[y][x]=1;
}
public void dfs(int Rx, int Ry){
if(table[Ry][Rx]==0){
return;
}
table[Ry][Rx]=0;
for(int i=0; i<4; i++){
int x = Rx+dx[i];
int y = Ry+dy[i];
if(x>=0 && y>=0 && x<M && y<N && table[y][x]==1){
dfs(x,y);
}
}
}
}
2667번과 매우 유사한 문제여서 설명을 짧게 하였는데 좀 더 이해가 필요하다면 아래의 글로가서 2667번의 설명도 봐보면 좋겠다.
https://parkjunbackend.tistory.com/54
b2667번
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지
parkjunbackend.tistory.com
정답코드는 아래와 같다.
package backjoon.b1012;
import java.util.*;
import java.io.*;
public class b1012 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int caseN = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
for(int i=0; i<caseN; i++){
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
Graph g = new Graph(M,N);
for(int j=0; j<K; j++){
st=new StringTokenizer(br.readLine());
int x= Integer.parseInt(st.nextToken());
int y= Integer.parseInt(st.nextToken());
g.addEdge(x,y);
}
int num=0;
for(int j=0; j<N; j++){
for(int k=0; k<M; k++){
if(g.table[j][k]==1){
g.dfs(k,j);
num++;
}
}
}
sb.append(num).append("\n");
}
System.out.println(sb);
}
}
class Graph{
int N;
int M;
int[][] table;
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};
public Graph(int M, int N){
table=new int[N][M];
this.N=N;
this.M=M;
}
public void addEdge(int x, int y){
table[y][x]=1;
}
public void dfs(int Rx, int Ry){
if(table[Ry][Rx]==0){
return;
}
table[Ry][Rx]=0;
for(int i=0; i<4; i++){
int x = Rx+dx[i];
int y = Ry+dy[i];
if(x>=0 && y>=0 && x<M && y<N && table[y][x]==1){
dfs(x,y);
}
}
}
}