카테고리 없음

백준 16469번 소년 점프 [JAVA]

javaju 2021. 12. 20. 17:27
 

16469번: 소년 점프

첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다. (2 ≤ R, C ≤ 100) 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다. 숫자 0은 이동 가능한

www.acmicpc.net

 

풀이 방법

세명의 위치가 주어질 때 한 지점에 세명이 모일 때의 최소가 되는 시간을 구하는 문제였습니다.

 

저는 세명의 정보를 큐에 넣어두고 상 하 좌 우로 움직이면서 방문하지 않은 곳이라면 map배열의 값을 하나 올려주었습니다. 해당 위치의 값이 3일 경우에는 세명 모두 해당 위치를 방문했으므로 time 배열에 해당 시간을 넣어주었습니다. 그리고 find() 메서드에서 가장 최소 시간을 찾고 그러한 지점의 개수를 함께 출력해주었습니다.

 

⭐100%에서 틀렸습니다가 나오신다면.. 반례로

2 2
00
00
1 1
1 2
2 2

넣어보세요! ㅎㅎ ⭐

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
 
public class Main {
    
    static class info{
        int x,y,time;
        boolean [][] visited;
        public info(int x, int y, int time, boolean[][] visited) {
            super();
            this.x = x;
            this.y = y;
            this.time = time;
            this.visited = visited;
        }
    }
    
    static int [][] map, time;
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
    
    static int R,C;
    static Queue<info> queue = new LinkedList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        map = new int[R][C];
        time = new int[R][C];
        
        for(int i=0;i<R;i++) {
            String line = br.readLine();
            for(int j=0;j<C;j++) {
                map[i][j] = line.charAt(j)-48;
                if(map[i][j]==1) map[i][j] = -1;
            }
        }
        
        for(int i=0;i<3;i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            
            queue.add(new info(x,y,0,new boolean[R][C]));
            map[x][y] = 1;
        }
        
        bfs();
        find();
    }
    
    public static void bfs() {
        
        
        while(!queue.isEmpty()) {
            info temp = queue.poll();
            temp.visited[temp.x][temp.y] = true;
            
            for(int i=0;i<4;i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];
                
                if(range(nx,ny) && map[nx][ny]!=-1 && !temp.visited[nx][ny]) {
                    temp.visited[nx][ny] = true;
                    map[nx][ny]++;
                    queue.add(new info(nx,ny,temp.time+1,temp.visited));
                    
                    if(map[nx][ny]==3) time[nx][ny] = temp.time+1;
                }                
            }
        }
    }
    
    public static boolean range(int x ,int y) {
        return x>=0 && x<R && y>=0 && y<C;
    }
    
    public static void find() {
        int min = Integer.MAX_VALUE, count=0;
        for(int i=0;i<R;i++) {
            for(int j=0;j<C;j++) {
                if(time[i][j]!=0 && min>time[i][j]) {
                    min = time[i][j];
                    count=1;
                }
                
                else if(min==time[i][j]) count++;
            }
        }
        
        if(min==Integer.MAX_VALUE) System.out.println("-1");
        else {
            System.out.println(min+"\n"+count);
        }
    }
}
 cs