[소프티어] Recovering the Region 자바 풀이 레벨2 (한양대 HCPC 2023) Jigsaw Sudoku 직소 스도쿠

[소프티어] Recovering the Region 자바 풀이 레벨2 (한양대 HCPC 2023) Jigsaw Sudoku 직소 스도쿠

 

https://softeer.ai/practice/9497

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

 

 

 

 

 

 

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

백준도 푼사람이 185명밖에 없네요

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

 

 

 

 

 

 

정답을 알고나면 어이가 없을지도 모르는 문제입니다.

 

 

 

 

문제 스펙

아직 푼사람이 6명밖에 없네요.

 

 

 

 

정답 코드

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

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

영역이 나뉘어져 있는 그림은 훼이크였다.

import java.io.*;
import java.util.*;

public class Main {

    public static int dx[] = {-1, 0, 1, 0};
    public static int dy[] = {0, 1, 0, -1};
    public static int n = 0;
    
    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());

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                System.out.print(i+1);
                if(j!=n-1) System.out.print(" ");
            }
            if(i!=n-1) System.out.println();
        }
    }

}

 

 

 

 

대회 공식 솔루션 문서에도 위 내용이 설명되어 있습니다.

 

 

 

 

실제로.dfs로 구현해도 동일한 결과값 나옵니다

 

 

 

 

 

 

 

훼이크에 당해서 dfs로 굳이 어렵게 맞춘 정답코드

import java.io.*;
import java.util.*;

public class Main {

    public static int dx[] = {-1, 0, 1, 0};
    public static int dy[] = {0, 1, 0, -1};
    public static int n = 0;
    
    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());

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


        int vCnt = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(v[i][j] == 0){ // 신대륙 발견
                    vCnt++; // 신대륙 개수 저장
                    v[i][j] = vCnt; // 신대륙 번호 지정
                    List<Integer> numSet = new ArrayList<>();
                    numSet.add(m[i][j]);
                    dfs(m, v, i, j, numSet, vCnt);
                }
            }
        }

        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                System.out.print(v[i][j]);
                if(j!=n-1) System.out.print(" ");
            }
            if(i!=n-1) System.out.println();
        }

        // for(int i=0; i<n; i++){
        //     for(int j=0; j<n; j++){
        //         System.out.print(i+1);
        //         if(j!=n-1) System.out.print(" ");
        //     }
        //     if(i!=n-1) System.out.println();
        // }
    }

    public static void dfs(int m[][], int v[][], int x, int y, List<Integer> numSet, int vCnt){
        for(int i=0; i<4; i++){
            for(int j=0; j<4; j++){
                int nx = x + dx[i];
                int ny = y + dy[j];
                if(nx < 0 || ny < 0 || nx >=n || ny >= n){
                    continue;
                }
                if(v[nx][ny] == 0 && !numSet.contains(m[nx][ny])){ // 신대륙이고, 넘셋에도 없으면
                    v[nx][ny] = vCnt;
                    numSet.add(m[nx][ny]);
                    dfs(m, v, nx, ny, numSet, vCnt);
                }
            }
            
                
        }
    }
}

 

 

 

 

백준도 둘다 정답처리 !!