[BOJ] 1012 - 유기농 배추 (Java)

알고리즘

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

1. 문제

• 배추밭에서 배추가 심어진 곳의 그룹 수 찾기
  

2. Idea

• DFS(Depth-First Search) 알고리즘 사용

3. 풀이

3.1. 변수 선언

• N, M, K: 배추밭의 크기와 배추의 위치를 저장하는 변수
• map[][]: 배추밭을 나타내는 2차원 배열
• dx, dy: 상하좌우 방향을 나타내는 배열
• visit: 각 위치의 방문 여부를 저장하는 배열
• cnt: 배추가 심어진 그룹의 개수

static int N;
static int M;
static int K;
static int map[][];
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
static boolean[][] visit;
static int cnt;

3.2. 각 테스트 케이스 순회 및 입력 저장

• BufferedReader, StringTokenizer을 사용하여 입력 처리
• 테스트 케이스의 개수 T를 입력받은 후, 각 테스트 케이스를 순회
• 각 테스트 케이스마다 배추밭의 크기(N, M)와 배추의 위치(K)를 입력받고, 배추 위치를 map 배열에 저장

		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;

        for(int t=0; t<T; t++){
            cnt = 0;
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[N][M];
            visit = new boolean[N][M];

            for(int i=0; i<K; i++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            } //배추 위치 입력

3.3. DFS 호출 및 결과 저장

• 각 배추 위치를 DFS를 이용하여 그룹을 형성하고, 그룹의 개수를 cnt에 저장

            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(map[i][j]==1 && !visit[i][j]){
                        DFS(i,j);
                        cnt++;
                    }
                }
            }

3.4. 결과 출력

System.out.println(cnt);

3.5. DFS 구현

• DFS(Depth-First Search) 알고리즘
  주어진 좌표 (x, y)에서부터 상하좌우로 인접한 위치를 탐색하며 그룹을 형성

1. 주어진 좌표 (x, y)에 대한 방문표시
2. 상하좌우로 이동하면서 다음 위치를 확인하고, 배추가 심어진 곳이고 아직 방문하지 않았다면 재귀적으로 DFS를 호출

• for 루프를 이용하여 상하좌우 네 방향을 모두 탐색
  next_x와 next_y: 현재 위치에서 상하좌우로 이동한 위치

3. 이동한 위치가 범위 내에 있는지 확인
4. 이동한 위치에 배추가 심어져 있고, 아직 방문하지 않았다면 DFS를 호출

    public static void DFS(int x, int y){
        visit[x][y] = true; //각 위치에 대한 방문표시

        for(int i=0; i<4; i++){ //상하좌우 인접한 위치 탐색
            int next_x = x + dx[i];
            int next_y = y + dy[i];
            // 이동한 위치가 범위 내에 있는지 확인
            if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < M) {
                if (map[next_x][next_y] == 1 && !visit[next_x][next_y]) { // 이동한 위치에 배추가 심어져 있고, 아직 방문하지 않았다면 DFS를 호출
                    DFS(next_x, next_y);
                }
            }
        }
    }

4. 전체코드

package alss3;
import java.util.*;
import java.io.*;

public class Week10{

    static int N;
    static int M;
    static int K;
    static int map[][];
	//상하좌우
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static boolean[][] visit; //방문처리를 위한 배열
    static int cnt;
    public static void main(String[] args) throws IOException{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;

        for(int t=0; t<T; t++){
            cnt = 0;
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[N][M];
            visit = new boolean[N][M];

            for(int i=0; i<K; i++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            } //배추 위치 입력

            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(map[i][j]==1 && !visit[i][j]){
                        DFS(i,j);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }

    }
    
    //DFS 함수 구현
    public static void DFS(int x, int y){
        visit[x][y] = true;

        for(int i=0; i<4; i++){
            int next_x = x + dx[i];
            int next_y = y + dy[i];
            if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < M) {
                if (map[next_x][next_y] == 1 && !visit[next_x][next_y]) {
                    DFS(next_x, next_y);
                }
            }
        }
    }
}