[SWEA] 1861 정사각형 방 자바(java) 풀이

sw expert academy 1861 정사각형 방 자바(java) 풀이

• 난이도 : D4
• sw expert academy 1861 정사각형 방 분배
  
  
  

문제정리

1. N²의 방이 존재 (최대 1000x1000 방이 존재)
2. i번째 줄 왼쪽에서 j번째 방에는 A_i,j가 적혀있다. (방 마다 모두 다르다)
3. 상하좌우로 방을 이동할 수 있다. ( 현재 방에 적힌 숫자보다 1 큰 경우만)

• 어떤 방에서 출발해야 가장 많이 이동할 수 있는지, 그렇다면 얼마만큼 이동 가능한지 출력!
  
  
  

문제풀이

• 이동할 수 있는 방의 개수가 최대인 방이 여러개 있다면, 적힌 수가 가장 작은 것 출력

1. dfs를 이용한다. 모든 점(i,j)에서 dfs 탐색을 한다.
   • visited는 i,j에 쓰여있는 숫자인 방번호로 방문했는지 안했는지 1차원 배열로 표현하여 관리한다.
   • visited[9]=true라면 방번호가 9인 방을 이미 방문함
2. max값이 더 크다면 max 값과 start값을 모두 update해주고, 같다면 시작점의 수를 비교해서 더 작다면 start를 update한다.

SWEA 1861 정사각형 방 분배 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.io.IOException;

class Pos{
    int x;
    int y;

    // constructor
    Pos(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class Solution {    
    static int[][] arr;
    static int n;
    static boolean[] visited;
    static int max;
    static int start;
    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 testNum = Integer.parseInt(br.readLine());

        for(int test=1; test<=testNum; test++){
            n = Integer.parseInt(br.readLine());

            // init for testcase
            arr = new int[n][n];
            max = 0;
            start = 101;

            // n개의 줄
            for(int i=0; i<n; i++){
                String[] temp = br.readLine().split(" ");

                // n개의 문자
                for(int j=0; j<n; j++){
                    arr[i][j] = Integer.parseInt(temp[j]);
                }
            }

            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    visited = new boolean[n*n+1];
                    int move = dfs(i,j);
                    if(max < move){
                        max = move;
                        start = arr[i][j];
                    }
                    else if(move != 0 && max == move){
                        // 시작점이 더 작은지 비교
                        if(arr[i][j] < start)   
                            start = arr[i][j];
                    }
                }
            }

            bw.write("#" + test + " " + start + " " + max);
            bw.newLine();
        }

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

    public static int dfs(int x, int y){
        // 상, 하, 좌, 우
        int[] xdir = {-1, 1, 0, 0};
        int[] ydir = {0, 0, -1 ,1};
        Stack<Pos> stack = new Stack<>();
        int move = 1;

        stack.push(new Pos(x, y));
        while(!stack.isEmpty()){
            Pos p = stack.pop();
            int a = p.x;
            int b = p.y;

            for(int i=0; i<4; i++){
                int dx = a + xdir[i];
                int dy = b + ydir[i];
                // 배열을 벗어나지 않았는지
                if(isValidPosition(dx, dy)){
                    // 방문하지 않았는지
                    if(!visited[arr[dx][dy]]){
                        // 다음 방문하려는 곳이 시작점보다 1이 큰지
                        if(arr[dx][dy] - arr[a][b] == 1){
                            visited[arr[dx][dy]] = true;
                            stack.push(new Pos(dx, dy));
                            move++;
                        }
                    }
                }
            }
        }

        return move;
    }

    public static boolean isValidPosition(int x, int y){
        if(x < 0 || x > n-1 || y < 0 || y > n-1)
            return false;
        return true;
    }
}