[99클럽 코테 스터디] 34일차 TIL DFS/BFS

 

 

오늘의 문제는 백준

 

11123번. 양 한마리... 양 두마리...

 

 

문제

 

 

 

문제 설명 

2차원 배열에서의 양의 무리 수를 세는 문제입니다. 그리드는 #은 양을 나타내고 .은 풀을 나타내며, 서로 연결된 #은 하나의 양 무리를 나타냅니다. 양이 몇 개의 무리로 나뉘어 있는지 출력해야 합니다. 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 56분이 걸렸습니다.

 

 

 

문제 접근 방식

연속으로 나열된 #을 하나의 양 무리로 간주하기 때문에 DFS를 사용합니다. 각 #에서 시작하여 연결된 모든 #을 방문하는 양의 무리를 탐색합니다. 2차원 배열을 사용해 그리드를 표현하고 탐색이 끝나면 양 무리의 수를 1 증가시킵니다. 

 

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static char[][] map;
    static boolean[][] visited;
    static int H, W;

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());  
        
        for (int t = 0; t < T; t++) {
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            H = Integer.parseInt(st.nextToken());  
            W = Integer.parseInt(st.nextToken()); 

            map = new char[H][W];
            visited = new boolean[H][W];

 
            for (int i = 0; i < H; i++) {
                String line = br.readLine();
                for (int j = 0; j < W; j++) {
                    map[i][j] = line.charAt(j);
                }
            }

            int sheepCnt = 0; 

            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] == '#' && !visited[i][j]) {
                        dfs(i, j);  
                        sheepCnt++;
                    }
                }
            }

            System.out.println(sheepCnt);  
        }
    }

    private static void dfs(int x, int y) {
        visited[x][y] = true;  

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < H && ny < W) {
                if (map[nx][ny] == '#' && !visited[nx][ny]) {
                    dfs(nx, ny);
                }
            }
        }
    }
}

 

 

자바 static 사용하기 

static 키워드는 자바에서 클래스 레벨에서 접근할 수 있는 메서드나 변수를 정의할 때 사용됩니다. 이 문제에서는 main과 dfs가 서로 공유하는 데이터 (dx, dy, map, visited, H, W)를 static으로 선언했습니다.

클래스의 모든 인스턴스가 동일한 데이터를 공유할 수 있게 해주고 프로그램의 전역 변수처럼 작동합니다. 문제 풀이에서는 별도의 객체를 생성할 필요가 없고, 모든 변수와 메서드를 클래스 레벨에서 접근할 수 있도록 static을 사용하였습니다. 

 

 

 

 

DFS 알고리즘 사용하기

DFS를 사용해 모든 #을 탐색합니다. DFS는 재귀적으로 현재 위치에서 갈 수 있는 모든 방향으로 이동하면서 양의 무리를 찾습니다. 이 과정에서 이미 방문한 위치는 visited 배열에 표시하여 중복 탐색을 방지합니다. DFS를 통해 하나의 양 무리의 모든 양을 탐색한 후, 다음 양 무리를 찾기 위해 반복문을 계속 진행합니다. 

 

 

 

 

 

 

이렇게 오늘 34일차 TIL을 작성해 보았습니다.