🎯 특정 조건을 만족하는 케이스 구하기

📌 프로그래머스 81302 거리두기 확인하기

public class 거리두기확인하기 {
    static class Solution {
        static final int NUM = 5;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        int sRow;
        int sCol;
        boolean[][] visited;
        String[][] room;
        boolean violate; // 핵심 포인트 1. 재귀 탈출 조건

        public int[] solution(String[][] places) {
            int[] answer = new int[NUM];
            int idx = 0;

            for(String[] pl : places){
                visited = new boolean[NUM][NUM]; // 핵심 포인트 2. 방문 배열
                room = new String[NUM][NUM];
                // places를 파싱하여 2차원 배열 room에 저장
                for(int i = 0; i < pl.length; ++i){
                    room[i] = pl[i].split("");
                }
                violate = false;
                // 반복문 조건에 탈출 조건을 더해줌으로써 쓸데없는 연산을 피할 수 있다
                for(int i = 0; i < NUM && !violate; ++i){
                    for(int j = 0; j < NUM && !violate; ++j){
                        // 응시자를 발견했다면 DFS 시작
                        if(room[i][j].equals("P")) {
                            sRow = i;
                            sCol = j;
                            dfs(i, j, 0);
                        }
                    }
                }
                answer[idx++] = violate ? 0 : 1;
            }

            return answer;
        }

        public void dfs(int r, int c, int step){ // 거리 2 이내에 사이에 파티션 없이 사람이 있다면 return false;
            if(violate || step > 2) return;
            if(r < 0 || r >= NUM || c < 0 || c >= NUM) return;
            if(visited[r][c] || room[r][c].equals("X")) return;
            visited[r][c] = true;
            if((r != sRow || c != sCol) && room[r][c].equals("P")) {
                violate = true;
                return;
            }
            for(int i = 0; i < dr.length; ++i){
                int nr = r + dr[i];
                int nc = c + dc[i];
                dfs(nr, nc, step + 1);
            }
        }
    }
}

가장 대표적인 유형으로 전형적인 DFS 문제의 성격을 띄고 있습니다.

• String[][] places를 파싱하여 대기실을 나타내는 2차원 배열로 치환할 수 있습니다.
• 대기실을 나타내는 2차원 배열의 크기가 5*5로 작습니다.
• 응시자들의 거리가 2 미만이여야 하는 특정 조건을 만족하는 대기실을 찾아내야 합니다.

✅ 이 유형을 풀 때 핵심 포인트

1. 방문을 체크할 수 있는 자료구조

이미 방문 했던 경로를 다시 방문할 필요는 없습니다.

2. 반복문 및 재귀 탈출 조건

쓸데없는 연산을 피하기 위해 조건을 만족하면 상태를 바꿔 탈출해줍시다.

🎯 구역의 갯수 세기

📌 백준 1012번 유기농 배추

public class Exam1012_유기농배추 {
    public static int T, M, N, K;
    /* T - 테스트 케이스
    M - 배추밭 가로길이
    N - 배추밭 세로길이
    K - 배추가 심어져 있는 위치의 개수
    */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = 0;
        T = Integer.parseInt(br.readLine());

        while (t < T) {
            StringTokenizer stMNK = new StringTokenizer(br.readLine());

            M = Integer.parseInt(stMNK.nextToken());
            N = Integer.parseInt(stMNK.nextToken());
            K = Integer.parseInt(stMNK.nextToken());

            int[][] farm = new int[M][N];

            for (int i = 0; i < K; i++) {
                StringTokenizer stmn = new StringTokenizer(br.readLine());
                int m = Integer.parseInt(stmn.nextToken());
                int n = Integer.parseInt(stmn.nextToken());
                farm[m][n] = 1;
            }

            bw.write(String.valueOf(solve(farm) + "\n"));

            t++;
        }

        bw.flush();

        br.close();
        bw.close();
    }

    public static int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 상하좌우

    public static int solve(int[][] farm) {
        int m = farm.length;
        int n = farm[0].length;
        int cnt = 0;

		// 이 문제의 포인트 1
        int[][] cab = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(dfs(farm, cab, i, j)) cnt++;
            }
        }

        return cnt;
    }

    public static boolean dfs(int[][] farm, int[][] cab, int m, int n) {
        if (m < 0 || m >= M || n < 0 || n >= N) return false;

        if (cab[m][n] == 1) return false;
        cab[m][n] = 1;

        if (farm[m][n] == 0) return false;

        for(int dir[] : dirs){
            int m1 = dir[0] + m;
            int n1 = dir[1] + n;

            dfs(farm, cab, m1, n1);
        }

		// 이 문제의 포인트 2
        return true;
    }
}

✅ 이 유형을 풀 때 핵심 포인트

1. 백트래킹 없이 DFS 시마다 계속해서 기록되는 방문 배열

지도 전체를 탐색하며 영역의 갯수를 세어줘야 하기 때문에 DFS 시작 지점이 달라도 같은 방문 배열을 사용합니다.

2. DFS 함수의 반환형은 boolean

재귀 함수가 중간에 있는 조건문을 통과하지 못하고 false를 반환 -> 영역이 존재하지 않습니다.
재귀 함수가 정상적으로 종료되어 true를 반환 -> 하나의 영역이 존재합니다.

해당 좌표에서 처음 dfs를 호출한 2중 for문 내부에서 조건문을 통해 영역의 갯수를 세어줘야합니다.

📌 프로그래머스 1829 카카오프렌즈 컬러링북

public class 카카오프렌즈컬러링북 {
    static class Solution {
        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0, -1, 0, 1};
        boolean[][] visit;
        int M, N;
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        int size;
        public int[] solution(int m, int n, int[][] picture) {
            M = m;
            N = n;

            visit = new boolean[m][n];

            for(int i = 0; i < m; ++i){
                for(int j = 0; j < n; ++j){
                    if(picture[i][j] != 0) {
                        size = 0;
                        if(dfs(picture, i, j, picture[i][j])) numberOfArea++;
                        maxSizeOfOneArea = Math.max(size, maxSizeOfOneArea);
                    }
                }
            }

            int[] answer = new int[2];
            answer[0] = numberOfArea;
            answer[1] = maxSizeOfOneArea;
            return answer;
        }

        public boolean dfs(int[][] picture, int r, int c, int target){
            // 이 문제의 포인트 1
            if(visit[r][c]) return false;
            if(picture[r][c] != target) return false;
            visit[r][c] = true;

            // 이 문제의 포인트 2
            size++;

            for(int i = 0 ; i < 4; ++i){
                int nr = r + dr[i];
                int nc = c + dc[i];
                if(nr >= 0 && nr < M && nc >= 0 && nc < N) dfs(picture, nr, nc, target);
            }

            return true;
        }
    }
}

바로 위의 '유기농 배추' 문제를 살짝 변형한 문제로

• '유기농 배추' 문제는 지도를 나타내는데 0과 1만을 사용했지만 이 문제는 0 이상 2^31 - 1 이하의 임의의 값을 사용합니다.
• 영역의 갯수를 세어주는 것은 동일하나, 그 영역 중 가장 큰 영역의 넓이를 구해야합니다.

이 두가지 목표를 달성하기 위해 포인트 1을 살펴보면 조건문의 순서가 달라진것을 알 수 있습니다.

0 이상 2^31 - 1 이하의 임의의 값을 사용하기 때문에 아까처럼 시작점의 데이터(target)과 일치여부를 검사하지 않고 방문여부를 체크한다면 현재와 다른 숫자를 target으로 할 때 이미 방문한 곳으로 여겨져 재귀를 빠져나오게 됩니다.

그래서 현재 지점이 시작점과 같은 데이터를 가졌는지 우선 확인하고 방문여부를 체크합니다.

조건문을 전부 만족했다면 같은 데이터로 이루어진 영역이기 때문에 size++ 해주어 재귀함수가 끝나면 최대 영역값을 저장하고 있는 maxSizeOfOneArea와 비교를 통해 최대값을 갱신해줍니다.