[SWEA] 1861 정사각형 방 - JAVA

1. 문제

SW Expert Academy

---

2. 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class D4_1861_정사각형방 {
    static int[][] deltas = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//상,하,좌,우 (행-열 순서)
    static int[][] rooms;
    static int N;

    static int maxRoom;
    static int maxMove;

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(in.readLine());

        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");

            N = Integer.parseInt(in.readLine());
            rooms = new int[N][N];
            maxRoom = 0;
            maxMove = 0;

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(in.readLine());
                for (int j = 0; j < N; j++) {
                    rooms[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    moveRoom(i, j, 1);
                }
            }
            sb.append(maxRoom).append(" ").append(maxMove).append("\n");
        }
        System.out.print(sb);
    }

    private static int moveRoom(int i, int j, int cnt) {
        for (int d = 0; d < 4; d++) {
            int ni = i + deltas[d][0];
            int nj = j + deltas[d][1];

            if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
            else if (rooms[i][j] + 1 != rooms[ni][nj]) continue;

            cnt = moveRoom(ni, nj, cnt + 1);

            if (maxMove < cnt) {
                maxMove = cnt;
                maxRoom = rooms[i][j];
            } else if (maxMove == cnt && maxRoom > rooms[i][j]) {
                maxRoom = rooms[i][j];
            }

            break;  //방에 있는 번호는 서로 다름
        }

        return cnt;

    }
}

처음에 visited[][] 배열을 사용해서 내가 이미 방문했는지 여부를 저장해두려고 했다. 하지만 이 문제의 조건 중에 "방마다 다른 번호"를 가지고 있고, "이동하려는 방에 적힌 숫자가 현재 방에 적혀있는 숫자보다 정확히 1 커야"한다는 게 있기때문에 갔던 곳을 또 방문할 확률이 없다는 걸 나중에 깨닫고 그 부분을 지웠다.

 

재귀함수의 동작은 다음과 같다.

1. 좌우상하 총 4번을 반복한다.

2. 범위를 벗어나거나 +1만큼 크지 않으면 넘어간다.

3. 다음 방에 방문하고(재귀호출), 그 반환값을 내 카운트값으로 새로 저장한다. 여기서 카운트값은 방에 방문한 횟수. 따라서 재귀호출 시에 현재 방문한 횟수+1해서 호출한다.

4. 최대값과 비교 후 반복문을 빠져나간다. (이동할 수 있는 방은 하나뿐이므로 더 이상 비교할 필요가 없음)

---

3. 결과

아래는 visited[][] 배열을 이용했던 코드다. 사용하지 않았을 때보다 코드길이나 실행시간이 많이 차이난다.