반응형

 

[광고 누르면 오늘의 행운 상승!!]

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWKaG6_6AGQDFARV&categoryId=AWKaG6_6AGQDFARV&categoryType=CODE

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

1. 참고사항
- 신호체계(몇초마다 달라지는 장애물)문제
- 자신의 cnt값 (이동한 거리) % 3 == 2 일때만 지나가게 한다. (소용돌이가 잠잠해지는 시간) 
- 소용돌이가 돌고있으면 제자리에 add한다.

2. 구현
- 4방향으로 bfs를 뻗어나간다.
- 소용돌이가 있다면 자신의 cnt값 (이동한 거리) % 3 == 2 일때만 지나간다.
- 소용돌이가 돌고있다면 제자리에 q.add를 한다(기다린다)
- 목적지에 도달하면 종료

package Study9;

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

public class 수영대회결승전 {
	static class Player{
		int row, col, cnt;
		public Player(int row, int col, int cnt) {
			this.row = row;
			this.col = col;
			this.cnt = cnt;
		}
	}
	public static int[] dx = {-1,0,1,0};
	public static int[] dy = {0,1,0,-1};
	static int[][] map;
	static boolean[][] visit;
	static int N,ans;
	static int SROW, SCOL, FROW, FCOL;
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		
		for (int tc = 1; tc <= T; tc++) {
			ans = 0;
			N = Integer.parseInt(br.readLine());
			
			map = new int[N][N];
			visit = 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());
			SROW = Integer.parseInt(st.nextToken());
			SCOL = Integer.parseInt(st.nextToken());
			
			st = new StringTokenizer(br.readLine());
			FROW = Integer.parseInt(st.nextToken());
			FCOL = Integer.parseInt(st.nextToken());
			
			if(SROW == FROW && SCOL == FCOL) {
				System.out.println("#" + tc + " " + 0);
				continue;
			}
			
			System.out.println("#" + tc + " " + (bfs() ? ans : -1));
		}
	}
	private static boolean bfs() {
		Queue<Player> q = new LinkedList<>();
		q.add(new Player(SROW, SCOL,0));
		visit[SROW][SCOL] = true;
		
		while(!q.isEmpty()) {
			Player player = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nx = player.row + dx[i];
				int ny = player.col + dy[i];
				
				if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
				
				if(nx == FROW && ny == FCOL) {
					ans = player.cnt+1;
					return true;
				}
				if(map[nx][ny] == 1 || visit[nx][ny]) continue;
				
				if(map[nx][ny] == 2) {
					if(player.cnt%3 == 2) {
						visit[nx][ny] = true;
						q.add(new Player(nx,ny,player.cnt+1));
					}else {
						visit[player.row][player.col] = true;
						q.add(new Player(player.row,player.col,player.cnt+1));
					}
				}else {
					visit[nx][ny] = true;
					q.add(new Player(nx,ny,player.cnt+1));
				}
			}
		}
		return false;
	}
}
반응형

+ Recent posts