[1861] 정사각형 방 in Java

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc 

SW Expert Academy

---

문제 조건

격자 크기 : N
1<= Aij <=N^2 (모든 방의 숫자는 모두 다름)
이동방향 : 상하좌우
이동 가능한 곳 : 방이 존재해야 함 & 현재 방에 적힌 숫자+1==이동하려는 방의 숫자
** 어떤 방에서 출발해야 가장 많은 개수의 방을 이동할 수 있는지 구하기 **
이동할 수 있는 방의 개수가 최대인 방이 여럿이라면? -> 방에 적혀있는 수가 가장 작은 것을 출력하기

 

접근 방식

- can_go 함수를 통해 이동할 수 있는 칸인지 체크

- move 함수 == dfs 기법 사용

 

 

 

 

시행 착오

- temp_cnt의 초기값이 0이 아닌 1이어야 하는 걸 생각하지 못했음.

(처음 시작한 위치 또한 카운팅 해줘야함)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
    static int[][] array;
    static boolean[][] visited;
    static int n;
    static int max_cnt; // 이동할 수 있는 방의 최대 개수
    static int mr;
    static int mc;
    static int temp_cnt; // 이동할 수 있는 방의 개수
    
    public static boolean can_go(int x,int y) {
        if (x>=0 && x<n && y>=0 && y<n && !visited[x][y]) return true;
        return false;
    }
    public static void move(int x,int y) {
        int[] dxs= {-1,1,0,0}; // 상,하,좌,우
        int[] dys= {0,0,-1,1}; 
        for(int i=0; i<4; i++) {
            int nx=x+dxs[i];
            int ny=y+dys[i];
            if (can_go(nx,ny)) {
                if (array[x][y]+1==array[nx][ny]) { // 현재 방에 적힌 숫자+1==이동하려는 방의 숫자
                    visited[nx][ny]=true;
                    temp_cnt++;
                    move(nx,ny);
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T= Integer.parseInt(br.readLine()); // 테스트 케이스의 수
        for (int t = 1; t <= T; t++) {
            n=Integer.parseInt(br.readLine()); // 격자 크기 : n
            array=new int[n][n]; // 배열 초기화
            mr=0; mc=0; // 출력값 초기화
            
            /* 1. 배열 입력받기 */
            for(int i=0; i<n; i++) {
                StringTokenizer st=new StringTokenizer(br.readLine());
                for(int j=0; j<n; j++) {
                    array[i][j]=Integer.parseInt(st.nextToken());
                }
            }
            max_cnt=1;
            
            /*2. 처음 위치 설정하기 */
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    visited=new boolean[n][n]; // 방문한 곳 초기화
                    temp_cnt=1;
                    move(i,j);
                    if (temp_cnt>max_cnt) { // 최대값 갱신
                        mr=i; mc=j;
                        max_cnt=temp_cnt;
                    }else if(temp_cnt==max_cnt) {
                        if (array[mr][mc]>array[i][j]) {
                            mr=i; mc=j;
                            max_cnt=temp_cnt;
                        }
                    }
                }
            }
            System.out.println("#"+t+" "+array[mr][mc]+" "+ max_cnt);
        }
    }
 
}