[JAVA] SWEA 4193 수영대회 결승전

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

SW Expert Academy

 

1. 서론

 

D4문제인데 어렵지 않다. 난 중간에 좀 막혀서 답들도 보고 했는데 근본적으로는 어렵지 않지만, 풀이에 대해서 꽤 고민하게 만드는 문제이다. BFS로 푸는 문제이다.

 

2. 문제풀이

 

NxN개의 배열을 시작점을 출발해서 도착점까지 도착하는데 걸리는 최소 시간을 구하는 문제이다. 즉, BFS로 최단 경로를 찾아내야 하는 문제이다. 시작점에서 도착점까지 장애물을 제외하고 원래 걸을 수 있는 길 + 소용돌이가 멈춘 시간의 길로 이동해 최단경로를 탐색하는 게 문제이다.

 

 

 

조건을 어떻게 처리해야 하는지 대충 감이 오는데 막상 돌려보니까 틀려서 황당했던 문제다. 남들은 다 소용돌이가 멈추는 시간을 n - 2 % 3 == 0 이 조건을 줘서 이거에 맞을 때까지 ++ 하고 그러더라. 그래서 내 코드가 틀린줄 알았는데 로직은 똑같이 돌아간다 ㅎㅎ

나는 클래스를 따로 정의했다. 좌표와 움직인 초, 그리고 다음 소용돌가 멈추는 초를 저장했다. 이유는 현 좌표에서 동서남북으로 탐색하는데 그때 한 좌표에서 많으면 4개씩 퍼져나가니까 그걸 depth 별로 내가 관리하기 어려울 것 같아서(그러면 dfs가 되므로?) 다른 사람들은 그래서 그냥 한 바퀴 돌 때마다 시간초를 ++ 했는데 나는 그냥 좌표마다 시간을 준 셈이다. (그래서 메모리를 좀 잡아먹은 듯 ㅎ)

 

설명이 조금 이해가 안갈 수 있어서 바로 백문이 불여일견으로.

 

 

 

 

 

3. 코드 설명

 

import java.awt.Point;
import java.io.*;
import java.util.*;


public class Solution {
	
	static int ans, n;
	static int[][] map;
	static Point start, end;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
	static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int q = 1; q <= t; q++) {
        	n = Integer.parseInt(br.readLine());
  
        	map = new int[n][n];
        	for (int i = 0; i < n; i++) {
        		StringTokenizer st = new StringTokenizer(br.readLine());
        		for (int j = 0; j < n; j++)
        			map[i][j] = Integer.parseInt(st.nextToken());
        	}
        	
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
        	start = new Point(x, y); //시작 좌표
        	st = new StringTokenizer(br.readLine());
        	x = Integer.parseInt(st.nextToken()); y = Integer.parseInt(st.nextToken());
        	end = new Point(x, y); //끝나는 좌표
        	
        	visit = new boolean[n][n]; //방문체크
        	ans = Integer.MAX_VALUE; //최솟값 저장
        	bfs(); //탐색
        	if (ans == Integer.MAX_VALUE) //도착할 수 없는 경우
        		ans = -1;
        	sb.append("#" + q + " " + ans + "\n");
        }
        bw.write(sb.toString());
        bw.close(); br.close();
    }
    
    public static boolean range(int nx, int ny) { //범위체크
    	if (nx >= 0 && nx < n && ny >= 0 && ny < n) return true;
    	return false;
    }
    
    public static void bfs() {
    	Queue<Swim> q = new ArrayDeque<>();
    	q.add(new Swim(start.x, start.y, 0, 2)); //시작점에서 시작
    	
    	while(!q.isEmpty()) {
    		Swim p = q.poll();
    		visit[p.x][p.y] = true; //방문처리
    		
    		if (p.x == end.x && p.y == end.y) //도착점에 도착하면
    			ans = Math.min(ans, p.cnt); //최솟값 체크
    		
    		for (int k = 0; k < 4; k++) {
    			int nx = p.x + dx[k], ny = p.y + dy[k];
    			if(range(nx, ny) && map[nx][ny] != 1 && !visit[nx][ny]) {//장애물이 없을 때
    				int cnt = p.cnt, w = p.w;
    				if (cnt == w) //w는 소용돌이를 지날 수 있는 시간을 가리킴
    					w += 3; //시간초가 소용돌이 지날 수 있는 시간과 같아졌다면 다음에 건널 수 있는 시간 지정
    				if (map[nx][ny] == 2 && cnt != w) //좌표가 소용돌이인데 소용돌이를 건널 수 없는 경우
    					q.add(new Swim(nx, ny, p.w + 1, p.w + 3)); //건널 수 있는 시간까지 기다린 다음에 이동, 즉 다음 소용돌이 열리는 시간 = cnt
    				else 
    					q.add(new Swim(nx, ny, p.cnt + 1, w)); //아무 것도 없는 경우
    			}	
    		}
    	}
    	return;
    }
}
class Swim {
	int x, y, cnt, w; //좌표, 몇 초 지났는지, 소용돌이가 가라앉는 초
	
	public Swim(int x, int y, int cnt, int w) {
		this.x = x;
		this.y = y;
		this.cnt = cnt;
		this.w = w;
	}
}

 

처음으로 소용돌이가 가라앉는 초는 2초다. 2초를 지정해두고 초가 소용돌이가 가라앉는 시간이 지날 때, 혹은 소용돌이를 만났을 때 +3으로 다음 소용돌이가 가라앉는 초로 시간을 바꿔치기해준다.

 

내가 테케 자꾸 틀렸던 부분이 w를 처리해주는 부분이 이었다. 처음에는 w만큼 초 지나면 다음 w를 설정하는 것을 안 했고, 그다음에는 장애물이 없는 경우와 소용돌이가 있는데  좌표가 소용돌이가 건널 수 있는 시간이면 앞에서 이미 +3 했기 때문에 보통 사람들과 큐의 들어가는 값이 같다는 점이 있었다. 테케도 딱 3개만 줘서 어쩌지도 못하다가 마음에 걸리는 부분을 수정하다 보니 됐다^^(이유를 몰라서 10트나 함) 그냥 속편하게 % 어쩌고 하는 코드가 나으려나...

 

로직이라기보단 이런 점이 좀 어려울 수도 있다는 생각이 들긴 하네... ㅎ