[소프티어] Recovering the Region 레벨2 자바 풀이 (한양대 HCPC 2023)

https://softeer.ai/practice/9497

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

 

백준 30875번 문제와 동일 문제.

https://www.acmicpc.net/problem/30875

 

문제를 보고 이해가 잘 되지 않았다. 이게 무슨 문제지 싶었다.

 

정답

그냥 N줄만큼 숫자 그대로 출력하면 정답이다.

원리: 직쏘 스도쿠는 세로줄/가로줄/영역 모두 다른 숫자로 구성되어 있기 때문이다.

 

하지만! DFS로도 해결 할 수 있다.

간만에 연습할겸 해당 문제를 DFS로 풀어보았다. 

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

    private static int n;
    private static int areaNo = 1;
    private static int[][] maps;
    private static int[][] visit;
    private static int[] dy = {-1, 1, 0, 0};
    private static int[] dx = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        maps = new int[n][n];
        visit = new int[n][n];

        // maps 입력 받기
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                maps[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 모든 칸을 방문하며 dfs 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 이미 방문한 경우 패스
                if (visit[i][j] != 0) continue;
                dfs(i, j, new ArrayList<>());
            }
        }

        // 출력
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                bw.write(visit[i][j] + " ");
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
    }

    public static void dfs(int y, int x, ArrayList<Integer> area) {
        // 구역의 크기가 n이라면 새로운 구역 번호로 증가
        if (area.size() == n) {
            areaNo++;
            return;
        }
        visit[y][x] = areaNo; // 현재 칸을 현재 구역으로 표시
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            // 범위를 벗어나는 경우 패스
            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
            // 이미 방문한 경우 패스
            if (visit[ny][nx] != 0) continue;
            // 현재 구역에 포함되어 있지 숫자면 추가 후 dfs 탐색
            if (!area.contains(maps[ny][nx])) {
                area.add(maps[ny][nx]);
                dfs(ny, nx, area);
            }
        }
    }
}

 

느낀점은 문제를 더 정확하게 이해해야했다. DFS 로 풀어보니 감회가 새로웠다.