[SWEA] 1861.정사각형 방

AngJ·2026년 8월 14일

코딩테스트

목록 보기

5/11

문제

요약

NxN의 배열이 있고 그 안엔 모두 다른 값의 숫자들이 배치되어있다.
A요소가 상하좌우의 다른 요소와 비교했을 때, 주변에 1 큰 수가 있다면 그 요소와 길을 이을 수 있다.
배열에서 이을 수 있는 길의 최대 길이와 그때의 시작 요소의 값을 출력
(최대 길이의 길이 여러개인 경우 시작 요소의 값이 작은 것을 출력)

접근

이 문제를 처음 봤을 때, 전체 모든 요소를 탐색해야하고, 시작 요소와 그 길의 최종 길이를 저장해서 값들을 비교해나가면 되겠다!는 생각으로 접근했다.

내가 다시 푼 풀이의 알고리즘은 아래와 같다.

알고리즘

완전 탐색 (시뮬레이션)

먼저 NxN의 배열 값들에 대한 iuput을 int형 2차원 배열에 저장

상하좌우를 탐색할 수 있게 dr, dc 배열 생성

배열의 요소들을 하나씩 선택해나가며 그 요소를 기준으로 주변 값들이 이어지는지 while 문으로 끝까지 탐색

탐색이 끝나면 지금까지의 최대 길의 길이와 현재 요소에서 이을 수 있는 길의 길이의 값 비교해 최댓값 갱신

모든 요소를 다 볼 때까지 반복

최종 코드

import java.util.*;
import java.io.*;
 
// 외길이니 BFS, DFS 쓰지 않는다. visited도 쓰지 않는다.
// 메모이제이션으로 이미 방문한 곳이라면 그 위치에서 갈 수 있는 거리만큼 cnt올린다.
 
class Solution {
    private static int[][] A;
    private static int N;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int testCase = 1; testCase <= T; testCase++) {
            N = Integer.parseInt(br.readLine()); // 1 ~ 1000
            A = new int[N][N];
             
            for (int i = 0; i < A.length; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < A.length; j++) {
                    A[i][j] = Integer.parseInt(st.nextToken());
                }
            }
             
            // 최대 이동할 수 있는 방의 개수
            int maxCnt = 0;
            // 최대 이동 가능 칸의 시작값
            int idx = Integer.MAX_VALUE; // 최대 이동을 위해 출발할 방 위치 (숫자) (작은 수를 찾아야 한다)
             
            // 모든 정점에서 출발해 갈 수 있는 칸으로 탐색
            for (int r = 0; r < A.length; r++) {
                for (int c = 0; c < A.length; c++) {
                    int cnt = go(r, c); // (r,c)에서 출발해 이동 가능한 칸 수
                    if (maxCnt < cnt || (maxCnt == cnt && idx > A[r][c])) {
                        maxCnt = cnt;
                        idx = A[r][c];
                    }
                }
            }
            sb.append("#").append(testCase).append(" ").append(idx).append(" ").append(maxCnt).append("\n");
        } // end of tc
        System.out.print(sb.toString());
    } // end of main
     
    private static int[] dr = {-1, 1, 0, 0}; // 상하좌우
    private static int[] dc = {0, 0, -1, 1};
     
    /**
     * A[r][c]에서 출발해 최대 이동할 수 있는 방의 개수를 리턴
     * @param r
     * @param c
     * @return
     */
    private static int go(int r, int c) {
        int cnt = 1; // r, c에서 이동할 수 있는 방의 개수
         
        while(true) {
            int nextNum = A[r][c] + 1;
            boolean flag = false; // 다른 칸으로 이동했는지 확인하는 플래그
             
            // 현재칸(r,c)에서 인접 칸을 탐색하는데 그 칸에 갈 수 있는가(나보다 1큰가?) - 자주 나오니 코드블럭으로 외울 것
            for (int i = 0; i < dr.length; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                // 배열범위 내인지는 항상 체크!
                if (nr >= 0 && nc >= 0 && nr < N && nc < N && nextNum == A[nr][nc]) {
                    r = nr;
                    c = nc;
                    cnt++;
                    flag = true;
                    break; // 상하좌우에서 1큰 값이 있다면 다른 곳엔 같은 값이 없기에 멈춘다! (안해도 풀리긴 하지만, 시간 절약을 위해 붙이는게 필요)
                }
            }
            if (!flag) break;
        }
         
        return cnt;
    }
} // end of class