[SWEA] 수영대회 결승전 (Java) 코드 및 풀이

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV

SW Expert Academy

 

오늘의 문제는 D4 난이도의 수영대회 결승전입니다.

3초마다 생기는 토네이도 때문에 조금 까다로웠던 문제입니다.

BFS를 활용해 풀 수 있었습니다.

 

풀이는 주석에 자세히 설명해두었습니다.

궁금한 점이나 피드백은 댓글에 남겨주세요!

 

정답 코드

package SSAFY_A형특강;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 가장 빠른길 - bfs
 * 장애물 1, 소용돌이 2
 * 최대한 0의 길로 가고,안되면 소용돌이
 * 소용돌이를 만나면 time 에 +2 해주기
 * 근데 어느길이 더 빠른지 모르니까 다 시도해봐야 한다.
 * 노드 클래스를 만들어 풀어야 할 것 같다. 각자 걸린 시간 정보를 가지고 있어야 하니까
 */
public class Solution_4193_수영대회결승전_최종버전 {
    static class Node {
        int r, c, time;
        public Node (int r, int c, int time) {
            this.r = r;
            this.c = c;
            this.time = time;
        }
    }

    // 4방 델타
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    static int N;

    static int[][] map;
    static boolean[][] visited;

    static Node start;
    static Node end;

    static int endTime; // 정답값 - 도착 노드까지 걸린 시간
    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            endTime = -1; // 정답값 초기화
            N = Integer.parseInt(br.readLine());

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

            // 시작점 도착점 입력 받기
            for (int i = 0; i < 2; i++) {
                st = new StringTokenizer(br.readLine());
                int r = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                if (i == 0) start = new Node(r, c, 0); // 시작점 설정
                else end = new Node(r, c, 0); // 도착점 설정
            }

            // 너비 우선 탐색 (bfs) 호출
            bfs();
            sb.append("#").append(tc).append(' ').append(endTime).append('\n');
        }
        System.out.println(sb);
    }

    private static void bfs() {
        Queue<Node> que = new ArrayDeque<>(); // 큐 생성
        que.add(start); // 시작점 큐에 넣기
        visited[start.r][start.c] = true; // 시작점 방문 처리
        while (!que.isEmpty()) {
            Node node = que.poll();

            // 종료 조건 : 현재 노드의 행, 열 좌표가 도착 노드의 그것과 같다면
            if (node.r == end.r && node.c == end.c) {
                endTime = node.time;
                return;
            }

            int r = node.r; // 현재 노드의 행 좌표
            int c = node.c; // 현재 노드의 열 좌표
            int time = node.time; // 현재 노드의 시간 정보
            for (int d = 0; d < 4; d++) { // 사방 탐색
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (isInRange(nr, nc) && !visited[nr][nc] && map[nr][nc] != 1) { // 범위 내에 있고, 방문한 곳이 아니며, 섬이 아니라면 큐에 넣기
                    // 만약 소용돌이를 만났다면 time에 +3 추가하기
                    if (map[nr][nc] == 2) {
                        if (time % 3 == 2) {
                            visited[nr][nc] = true; // 방문 처리
                            que.add(new Node(nr, nc, time + 1));
                        }
                        else {
                            visited[r][c] = true; // 방문 처리
                            que.add(new Node(r, c, time + 1));
                        }
                    }
                        // 소용돌이가 아니라면 +1 추가하기
                    else {
                        visited[nr][nc] = true; // 방문 처리
                        que.add(new Node(nr, nc, time+1));
                    }
                }

            }
        }
    }

    private static boolean isInRange(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < N;
    }
}