[SWEA/Java] 1861. 정사각형 방

[SWEA/Java] 1861. 정사각형 방

SW Expert Academy

---

문제 해석

이 문제는 N x N 크기의 방에서 시작하여, 상하좌우로 이동할 때 각 방의 번호가 1씩 증가하는 경로를 최대한 많이 찾는 문제이다. 최종 목표는 시작 방 번호가 가장 작은 경로 중, 최대 이동 횟수를 가진 경로를 찾는 것이다.

풀이 과정

풀이는 너비 우선 탐색(BFS)을 기반으로 구현되었다. 각 방에서 시작하여, 가능한 모든 방향으로 이동하면서 조건에 맞는 방으로만 이동하도록 하였다. 이 때, 이동 가능한 방의 개수와 시작 방 번호를 저장하기 위해 우선순위 큐를 사용하였다. 이 큐는 이동 횟수가 많은 것을 기준으로 정렬하며, 이동 횟수가 같을 경우 방 번호가 작은 것을 기준으로 정렬된다.

코드

package edu.ssafy.im.SWEA.D4.No1861;

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

public class Solution {
    int[][] graph; // 방 번호 저장 배열
    boolean[][] visited; // 방문 여부를 확인하는 배열
    int n; // 방의 크기
    int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 이동 가능한 방향 (상하좌우)
    PriorityQueue<Point> pq; // 최대 이동 거리를 저장할 우선순위 큐

    public static void main(String[] args) throws IOException {
        new Solution().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int testCase = Integer.parseInt(br.readLine()); // 테스트 케이스 수

        for (int t = 1; t <= testCase; t++) {
            n = Integer.parseInt(br.readLine()); // 방의 크기

            graph = new int[n][n]; // 방 번호를 저장할 배열 초기화
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken()); // 방 번호 입력
                }
            }

            pq = new PriorityQueue<>(
                    (o1, o2) -> {
                        if (o1.cnt == o2.cnt) {
                            return graph[o1.x][o1.y] - graph[o2.x][o2.y];
                        }
                        return o2.cnt - o1.cnt;
                    }
            );
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    visited = new boolean[n][n];
                    bfs(i, j, 1); // BFS를 이용해 각 방에서 시작하는 최대 이동 횟수 계산
                }
            }

            Point p = pq.poll(); // 가장 많이 이동한 결과를 가져옴
            int ans = p.cnt;
            int roomNo = graph[p.x][p.y];
            sb.append("#").append(t).append(" ").append(roomNo).append(" ").append(ans).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void bfs(int x, int y, int cnt) {
        Queue<Point> queue = new ArrayDeque<>();
        queue.offer(new Point(x, y, cnt));
        visited[x][y] = true;
        pq.offer(new Point(x, y, cnt));

        while (!queue.isEmpty()) {
            Point p = queue.poll();

            if(p.cnt >= pq.peek().cnt) pq.offer(new Point(x, y, p.cnt));

            for (int d = 0; d < direction.length; d++) {
                int nx = p.x + direction[d][0];
                int ny = p.y + direction[d][1];

                if (checkStatus(nx, ny)) {
                    if (graph[nx][ny] - graph[p.x][p.y] == 1) {
                        visited[nx][ny] = true;
                        queue.offer(new Point(nx, ny, p.cnt + 1));
                    }
                }
            }
        }
    }

    private boolean checkStatus(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < n && !visited[x][y];
    }


    class Point {
        int x;
        int y;
        int cnt;

        public Point(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N^2 * M)이다. 여기서 N은 방의 크기이며, M은 최대 이동 가능한 횟수이다. 모든 방을 시작점으로 사용하여 BFS를 수행하기 때문에 N^2개의 시작점에 대해 최대 M번의 이동을 수행할 수 있다.

느낀점

이 문제를 통해 BFS를 사용하여 문제를 효과적으로 해결할 수 있음을 알 수 있었다. 다양한 조건과 제한 사항을 처리하는 능력을 키우는 좋은 기회였으며, 알고리즘의 효율성을 높이는 방법에 대해 더 고민할 수 있는 계기가 되었다.