SWEA 4193 수영대회 결승전(JAVA) 🏊‍♀️

문제 링크

SW Expert Academy

문제 설명

도착지까지의 최소 시간 구하기

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 수영장의 크기 N  ( 2<=N<=15 )
다음 N개의 줄의 i번째 줄에는 수영장의 모양이 공백으로 구분되어 주어진다. ( 0 : 지나갈 수 있는 곳 , 1 : 장애물 , 2: 주기가 2초인 소용돌이)
다음으로 시작위치 A, B가 주어지고 ( 0 <=A, B <=N-1)
마지막 줄에 도착 위치 C, D가 주어진다 ( 0 <=C, D <=N-1) ( 도착점과 시작점은 소용돌이가 아니다 )

출력

각 테스트 케이스마다 테스트 케이스의 번호와 이동시간을 공백을 두고 표시한다 
도착할 수 없다면 -1을 출력한다.

구조화

bfs로 도착지까지 진행

주의 사항

소용돌이일 경우 time이 3의 배수여야함 -> 시작부터 time++을 해서 3의 배수로 맞출 수 있었음

소스 코드

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

public class Solution_4193_수영대회결승전 {

	static int T, N, result, startR, startC, endR, endC;
	static int[][] map;
	static boolean[][] visited;
	// 상 하 좌 우
	static int[][] way = {{-1,0},{1,0},{0,-1},{0,1}};
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		
		// test case
		for (int t = 1; t <= T; t++) 
		{
			N = Integer.parseInt(br.readLine());
			
			map = new int[N][N];
			visited = new boolean[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());
				}
			}
			
			st = new StringTokenizer(br.readLine());
			startR = Integer.parseInt(st.nextToken());
			startC = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			endR = Integer.parseInt(st.nextToken());
			endC = Integer.parseInt(st.nextToken());
			
			bfs();
			System.out.printf("#%d %d%n",t,result);
		}
		// --- test case ---
	}
	
	private static void bfs() {

		int time = 0;
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {startR, startC});
		
		while(!q.isEmpty())
		{
			int size = q.size();
			time++;
			while(size-- > 0)
			{
				int[] cur = q.poll();
				int cr = cur[0];
				int cc = cur[1];
				visited[cr][cc] = true;
				
				if(cr==endR && cc==endC)
				{
					result = time-1;
					return;
				}
				for (int i = 0; i < 4; i++) 
				{
					int nr = cr+way[i][0];
					int nc = cc+way[i][1];
					
					// 경계 체크
					if(!isRight(nr,nc)) continue;
					if(visited[nr][nc]) continue;
					if(map[nr][nc]==1) continue;
					// 소용돌이
					if(map[nr][nc]==2)
					{
						// 지나갈 수 있음
						if(time%3==0)
						{
							q.offer(new int[] {nr, nc});
						}
						// 지나갈 수 없음
						else
						{
							q.offer(new int[] {cr, cc});
						}
					}
					else if(map[nr][nc]==0)
					{
						q.add(new int[] {nr, nc});
					}
				}
			}
			
		}
		result=-1;
	}

	private static boolean isRight(int nr, int nc) {
		return (nr>=0 && nr<N && nc>=0 && nc<N);
	}

}

비슷한 문제

SW Expert Academy