[백준/JAVA] 20926 - 얼음미로

문제 정보

https://www.acmicpc.net/problem/20926

 

문제

문제 해결과정

문제 분석 및 시간복잡도 계산

1. 출발점 ~ 도착점까지의 최단시간을 구하는 '최단경로' 문제였다.

2. 정점 사이의 (인접한 두 좌표간의) 가중치(미끌시간)이 달랐다. ⇒ BFS를 사용할 수 없다. (BFS는 가중치가 동일해야 함)

3. 각 가중치는 0이상 9이하라고 주어졌으므로, 가중치가 양수였다. ⇒ '다익스트라'와 '플로이드워셜' 모두 사용 가능

• 다익스트라 : '시작점 ~ 다른 모든 정점' 사이의 최단거리 구함. 시간복잡도는 O(E*logV)
• 플로이드워셜 : '모든 정점 쌍' 사이의 최단거리 구함. 시간복잡도는 O(V^3)
• 시간복잡도는 이전 블로그 포스팅을 참고

4. 출발점과 도착점이 주어졌으므로, 시간복잡도가 더 유리한 '다익스트라' 방식을 채택하기로 하였다.

• 다익스트라의 경우 O(E*logV) = O(4*500*500*log(500)) = O((10^6) * log(500))
• 플로이드워셜의 경우 O(V^3) = O(500^3) = O((10^6) * 125)
• 사실상 인접한 네 방향으로 간선은 있지만, 결국 우선순위큐에 추가/삭제되는 것은 인접한 방향으로 미끄러지다가 바위에 부딪혔을때의 정점이다. 따라서, 실제 시간복잡도에 영향을 주는 (이웃한) 간선의 개수(E)는 더 작을 것으로 예상된다. 

 

구현 과정

1. 변수 정의

• 방문배열(visited) : 해당 지점을 방문했는지 여부 저장
  • 방문했다 == 시작점 ~ 해당 노드까지의 최단 거리 결정됐다
• 거리배열(dist) : 시작점부터 해당 지점까지의 최단거리를 저장
• 최소힙(q) : 현재 바위에 부딪혀서 멈춘 지점의 정보 저장 (Node : x좌표, y좌표, 소요시간)

2. 초기화

• 거리 배열(dist)를 아주 큰 값(INF)로 초기화하고, 시작점 값만 0으로 설정합니다.
• 출발지를 최소힙(우선순위 큐)에 넣습니다. 

3. 반복

• 힙에서 최솟값(루트)를 고릅니다. 이때 힙에서 해당 노드는 힙에서 삭제됩니다.
  • 뽑힌 노드가 출구(Exit)이면 종료 
  • 이미 방문한 지점이라면, 다시 반복의 시작으로 돌아갑니다.
  • 방문하지 않은 지점이라면, 방문처리를 합니다. (시작점 ~ 해당 노드까지의 최단거리는 정해졌다)
• 뽑힌 노드에 인접한(상하좌우) 노드들을 보며, 해당 방향으로 쭉~ 미끄러집니다.
  • 절벽에 떨어지거나 / 구멍에 빠진 경우에는, 그 다음 인접한 노드를 봅니다.
  • 바위에 부딪힌 경우, 'dist[뽑힌 노드] + 가중치합(바위 앞까지 미끌시간합)'과 'dist[바위 앞 노드]'를 비교하여 'dist[바위 앞 노드]'를 더 작은 값으로 갱신해줍니다. 이때, 갱신되었다면 다시 힙에 해당 노드를 추가합니다.
  • 출구인 경우, 'dist[뽑힌 노드] + 가중치합(출구 앞까지 미끌시간합)'과 'dist[출구]'를 비교하여 'dist[출구]'를 더 작은 값으로 갱신해줍니다. 이때, 갱신되었다면 다시 힙에 해당 노드를 추가합니다.

4. 종료

• 힙이 비었거나 출구(Exit)를 만났다면 반복이 종료되고, 출발지에서 도착지까지의 최단 거리가 결정됩니다. (도착지에 도착할 수 없는 경우 -1)

 

코드

class Node implements Comparable<Node>{
	int x;
	int y;
	int time;
	
	public Node(int x, int y, int time) {
		this.x = x; this.y = y; this.time = time;
	}
	
	@Override
	public int compareTo(Node o) {
		return this.time - o.time;
	}
}

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 맵의 크기 입력받기
		StringTokenizer st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		
		// 맵 생성
		int startx = -1, starty = -1, finishx = -1, finishy = -1;
		char[][] map = new char[n][m];
		for(int r=0; r<n; r++) {
			String s = br.readLine();
			for(int c=0; c<m; c++) {
				map[r][c] = s.charAt(c);
				
				// 시작점, 도착점 기록
				if(map[r][c] == 'T') {
					startx = r; 
					starty = c;
				} else if(map[r][c] == 'E') {
					finishx = r;
					finishy = c;
				}
			}
		}
		
		/* 초기화 */
		// 방문배열 : 해당 지점 방문 여부 저장
		boolean[][] visited = new boolean[n][m];
		
		// 거리배열 : 시작점 ~ 해당지점까지의 최단시간 저장
		int[][] dist = new int[n][m];
		for(int i=0; i<n; i++) {
			// 모든 거리를 MAX값으로 초기화
			Arrays.fill(dist[i], Integer.MAX_VALUE);
		}
		dist[startx][starty] = 0; // 시작점만 0으로
			
		// 최소힙 : 현재 바위에 부딪혁서 멈춘 지점의 정보(좌표 + 시간) 저장
		PriorityQueue<Node> q = new PriorityQueue<>();
		// 시작점 넣음
		q.offer(new Node(startx, starty, 0));
        
		
		/* 반복 */
		int minTime = -1; // 최단 탈출 시간 (도착하지 못한 경우 : -1)
		while(!q.isEmpty()) {	
			// 최소힙에서 하나 꺼냄(시간 최솟값)
			Node cur = q.poll();
			
			// 도착지점이라면 => break
			if(cur.x == finishx && cur.y == finishy) {
				minTime = dist[finishx][finishy];
				break;
			}
			
			// 이미 방문한지점이라면 => pass
			if(visited[cur.x][cur.y]) continue;
            
			visited[cur.x][cur.y] = true; // 지점 방문 했다 == 최단시간 정해졌다
			
			// 이 정점과 이웃한(상하좌우 인접) 방향으로 미끄러짐
			for(int i=0; i<4; i++) {
				Node result = slide(i, cur.x, cur.y, cur.time, map, n, m); // 그 다음 멈추는 좌표 + 이동시간
				
				// 1) 절벽에 떨어지거나 / 구멍에 빠진 경우
				if(result == null) continue;
				
				// 2) 바위에 부딪히거나 / 출구 만난 경우
				// 큐에서 꺼냈을 때의 지점(해당 지점은 포함 x) ~ 바위 앞/출구까지의 미끌시간의 합 < 현재 바위 앞/출구의 시간배열의 시간 
				if(!visited[result.x][result.y] && result.time < dist[result.x][result.y]) {
					dist[result.x][result.y] = result.time;
					q.offer(result);
				}
			}
		}
        
		
		/* 출력 */
		System.out.println(minTime);
	}
	
	// 방향벡터(상하좌우)
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	static Node slide(int dir, int x, int y, int time, char[][] map, int n, int m) {
		int len = 1;
		int sum = 0;
		while(true) {
			int nextx = x + len*dx[dir];
			int nexty = y + len*dy[dir];
			
			// 1) 중간에 절벽 / 구멍 만나는 경우 => 종료
			if(nextx<0 || nextx>=n || nexty<0 || nexty>=m || map[nextx][nexty] == 'H') {
				return null;
			}

			// 2) 중간에 바위 만나는 경우
			if(map[nextx][nexty] == 'R') {				
				// 바위 바로 앞 좌표 + 걸린 시간 반환
				nextx = x + (len-1)*dx[dir];
				nexty = y + (len-1)*dy[dir];				
				return new Node(nextx, nexty, time + sum);
			}
			// 3) 출구 만나는 경우
			else if(map[nextx][nexty] == 'E') {				
				// 출구 좌표 + 걸린 시간 반환			
				return new Node(nextx, nexty, time + sum);
			}
			
			sum += map[nextx][nexty] - '0';
			len++;
		}
	}
}