[코딩테스트] SWEA 1226 미로1(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 1226 미로1입니다.

포인트

• 먼저 시작점과 목표 지점을 설정합니다.
• 시작점으로부터 상하좌우 방향으로 이동 가능한지를 순회하면서 탐색을 진행합니다.
• 이동 중에는 벽은 갈 수 없도록 범위 체크를 합니다.
• 또한 이미 방문한 구간은 다시 탐색하지 않도록 처리하여 중복을 방지합니다.

위 조건을 기반으로, 너비 우선 탐색(BFS)를 사용해 전체 경우를 탐색합니다.

소스코드

package SWExpert.Implementation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Q1226 {
    static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    private static int tc = 10, ROW = 16, COL = 16;
    private static int[][] miro;
    private static boolean[][] visited;
    private static Pair start, end;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= tc; t++) {
            br.readLine();
            init();
            for (int i = 0; i < ROW; i++) {
                String line = br.readLine();
                for (int j = 0; j < COL; j++) {
                    miro[i][j] = line.charAt(j) - '0';
                    if (miro[i][j] == 2) {
                        start = new Pair(i, j);
                    } else if (miro[i][j] == 3) {
                        end = new Pair(i, j);
                    }
                }
            }

            adventure();

            sb.append("#").append(t).append(" ").append(visited[end.x][end.y] ? 1 : 0).append("\n");
        }
        System.out.println(sb);
    }

    private static void adventure() {
        Queue<Pair> q = new LinkedList<>();
        q.add(start);
        visited[start.x][start.y] = true;

        while (!q.isEmpty()) {
            Pair cur = q.poll();

            for (int idx = 0; idx < 4; idx++) {
                int nx = cur.x + dx[idx];
                int ny = cur.y + dy[idx];
                if (canGo(nx, ny)) {
                    visited[nx][ny] = true;
                    q.add(new Pair(nx, ny));
                }
            }
        }
    }

    private static boolean canGo(int x, int y) {
        if (!inRange(x, y)) {
            return false;
        }

        if (visited[x][y] || miro[x][y] == 1) {
            return false;
        }

        return true;
    }

    private static boolean inRange(int x, int y) {
        return 0 <= x && x < ROW && 0 <= y && y < COL;
    }

    private static void init() {
        miro = new int[ROW][COL];
        visited = new boolean[ROW][COL];
    }
}

코드 설명

• Pair 클래스
  BFS 탐색을 위해 (x, y) 위치를 저장하는 단순한 좌표 클래스
• main() 함수
  • 한 테스트 케이스마다 미로를 입력받고, 2는 시작점, 3은 도착점으로 저장합니다.
  • adventure() 함수를 통해 BFS로 탐색을 수행합니다.
  • 최종적으로 도착 지점을 방문했는지 여부에 따라 1 또는 0을 출력합니다.

• adventure() 함수
  BFS 탐색
  
  • BFS 큐를 통해 너비 우선 탐색을 수행합니다.
  • 다음 위치 (nx, ny)가 갈 수 있는 위치이면 큐에 추가하고 방문 처리합니다

• init()
  테스트케이스에 따른 초기화 함수(miro 배열, visited 배열)
• inRange(int x, int y)
  x, y가 격자 내에 있는지 판단하는 함수
  • ROW와 COL을 기준으로 좌표가 16×16 격자 안에 있는지 확인합니다.
• canGo(int x, int y)
  다음 칸을 갈 수 있는지 판단
  • 격자 범위를 벗어나지 않았고
  • 아직 방문하지 않았으며
  • 벽(1)이 아니라면 true 반환