[구름 | Java Lv.3] [현대모비스][예선] 주차시스템 (탐색)

문제

https://level.goorm.io/exam/152115/%ED%98%84%EB%8C%80%EB%AA%A8%EB%B9%84%EC%8A%A4-%EC%98%88%EC%84%A0-%EC%A3%BC%EC%B0%A8%EC%8B%9C%EC%8A%A4%ED%85%9C/quiz/1

구름LEVEL

---

접근

1이 아닌 구역들을 dfs로 구하고, 각 구역마다의 점수를 계산하면 되겠다. 

package week7.baek.search;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class ParkingSystem {
    static ArrayList<String> scope = new ArrayList<>();
    public static void dfs(int[][] map, boolean[][] visited, int x, int y, String path){
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        //방문 처리
        visited[x][y] = true;

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

            if(nx < 0 || ny < 0 || nx >= map.length || ny >= map[0].length) {
                continue;
            }
            if(!visited[nx][ny] && map[nx][ny] != 1){
                dfs(map, visited, nx, ny, path + map[nx][ny] );
                count++;
            }
        }

        //방문한 곳이 없다면, 영역 끝난 것
        if(count == 0){
            scope.add(path);
//            System.out.println(path);
        }

    }
    public static void main(String[] args) throws Exception {
        //입력값 저장
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int N = Integer.parseInt(input.split(" ")[0]);
        int M = Integer.parseInt(input.split(" ")[1]);

        int[][] map = new int[N][M];
        for (int i = 0; i < N; i++) {
            input = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(input.split(" ")[j]);
            }
        }

        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j] != 1 && !visited[i][j]){
                    dfs(map,visited, i, j, String.valueOf(map[i][j]));
                }
            }
        }

        System.out.println(scope);
        //점수 계산
    }
}

 

수정 후 최종 코드

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

public class Parking {
    static int n, m;
    static int[][] parkingLot;
    static boolean[][] visited;
    static int maxScore = 0;
    static int[] dx = {-1, 1, 0, 0};  // x 방향 이동
    static int[] dy = {0, 0, -1, 1};  // y 방향 이동

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());  // 세로 크기
        m = Integer.parseInt(st.nextToken());  // 가로 크기

        parkingLot = new int[n][m];  // 주차장 상태를 저장할 2차원 배열
        visited = new boolean[n][m];  // 방문 여부를 확인할 배열

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                parkingLot[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && parkingLot[i][j] != 1) {
                    int score = dfs(i, j);  // 현재 구역의 점수를 계산
                    maxScore = Math.max(maxScore, score);  // 최대 점수 갱신
                }
            }
        }

        System.out.println(Math.max(maxScore, 0));  // 결과 출력
    }

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

        if (parkingLot[x][y] == 0) score += 1;
        else if (parkingLot[x][y] == 2) score -= 2;

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

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && parkingLot[nx][ny] != 1) {
                score += dfs(nx, ny);
            }
        }
        return score;
    }
}