[Baekjoon] 16469_소년 점프

Gold IV

문제(출처: https://www.acmicpc.net/problem/16469)

---

< 소년 점프 >

 

문제 풀이

 

악당의 각 위치부터 시작해서 상하좌우로 움직여 각 지점마다 최소 시간을 구해둔다. 

그 후에 전체를 탐색하여 3명 다 방문한 곳이며 시간이 최소인 시간을 구한다. 

 

 

 - my solution (Java)

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

public class _16469_ { // 소년 점프
	static int arr[][], visited[][][], r, c;
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		r=Integer.parseInt(st.nextToken());
		c=Integer.parseInt(st.nextToken());
		
		arr=new int[r][c];
		visited=new int[r][c][3];
		
		for(int i=0; i<r; i++) {
			String s=bf.readLine();
			for(int j=0; j<c; j++) {
				arr[i][j]=s.charAt(j)-'0';
				for(int k=0; k<3; k++) {
					visited[i][j][k]=-1;
				}
			}
		}
		
		for(int i=0; i<3; i++) {
			st=new StringTokenizer(bf.readLine());
			int x=Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			bfs(x-1 ,y-1, i);
		}
		
		int result=0, min_val=Integer.MAX_VALUE;
		for(int i=0; i<r; i++) {
			for(int j=0; j<c; j++) {
				if(visited[i][j][0] !=-1 && visited[i][j][1] !=-1 && visited[i][j][2] !=-1) {
					int temp=visited[i][j][0];
					if(temp<visited[i][j][1]) temp=visited[i][j][1];
					if(temp<visited[i][j][2]) temp=visited[i][j][2];
					
					if(min_val>temp) {
						min_val=temp;
						result=1;
					}else if(min_val==temp) {
						result+=1;
					}
				}
			}
		}
		if(result==0) {
			System.out.println(-1);
		}else {
			System.out.println(min_val);
			System.out.println(result);
		}
		
	}

	private static void bfs(int x, int y, int num) {
		Queue<int[]> queue=new LinkedList<>();
		visited[x][y][num]=0;
		queue.add(new int[] {x,y,0});
		
		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			for(int i=0; i<4; i++) {
				int x1=temp[0]+dx[i];
				int y1=temp[1]+dy[i];
				if(x1>=0 && x1<r && y1>=0 && y1<c && arr[x1][y1]==0) {
					if(visited[x1][y1][num]==-1) {
						visited[x1][y1][num]=temp[2]+1;
						queue.add(new int[] {x1,y1, temp[2]+1});
					}
				}
			}
		}
	}
}

 

• Main
  • r, c 입력
  • arr : 미로 
    visited: 방문 최단 시간 (-1로 초기화)
  • 3명의 좌표 입력받은 후 bfs 탐색
  • visited 순환하면서 3차원의 값이 다 -1 아님 & 최솟값
    최솟값 udpate : min_val update 및 result =1
    최솟값과 same : result += 1
  • result 가 0이면 세 악당이 모일 수 없는 것이므로 -1 출력
    0이 아니면 최소 값과 지점의 개수 출력
• bfs
  
  • queue에 초기 위치 저장 및 visited 값 0으로 저장
  • queue가 빌 때까지 반복 -> 상하좌우로 이동하여 미로 안이고 이동 가능한 길이며 아직 방문하지 않은 곳이라면 걸린 시간 저장 및 queue에 저장

---

생각🤔

 

문제를 이해하는데 시간이 조금 걸렸지만 코드는 쉽게 구현할 수 있었다.

 

---