[백준] 14940 쉬운 최단거리 - BFS

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

14940번: 쉬운 최단거리

 

문제풀이

BFS 문제였습니다.

다만, 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

이 값이 엄청나게 크기에 Scanner 로 값을 입력받으면 시간초과가 납니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
 
st = new StringTokenizer(br.readLine()); 
map[i][j] = Integer.parseInt(st.nextToken());

BufferedREader와 StringTokenizer를 사용해서 진행해야합니다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	
	public static int R, C, N;
	public static int[][] map;
	public static int[][] result;
	public static boolean[][] visited;
	public static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) throws IOException {
    	
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
//    	Scanner sc = new Scanner(System.in);
//    	R = sc.nextInt();
//    	C = sc.nextInt();
    	map = new int[R][C];
    	result = new int[R][C];
    	visited = new boolean[R][C];
    	int startx=0, starty=0;
    	for(int i=0;i<R;i++) {
    	    st = new StringTokenizer(br.readLine()); 
    		for(int j=0;j<C;j++) {
//    			map[i][j] = sc.nextInt();
    	        map[i][j] = Integer.parseInt(st.nextToken());
    			//2 지점을 큐에 넣고 BFS를 돌리기 위한 세팅을 합니다. 
    			if(map[i][j] == 2) {
    				q.offer(new Node(i, j, 0));
    				result[i][j] = 0;
    				startx=i;
    				starty=j;
    			}
    		}
    	}
    	
    	BFS(startx, starty);
 
    	for(int i=0;i<R;i++) {
    		for(int j=0;j<C;j++) {
    			if(visited[i][j] == true || map[i][j] == 0) {
    				System.out.print(result[i][j]+ " ");
    			}
    			else if(visited[i][j] == false && map[i][j] != 0) System.out.print("-1 ");
    		}
    		System.out.println();
    	}
    	
    }
    
    public static void BFS(int startx, int starty) {
    	int[] dx= {-1,1,0,0};
    	int[] dy= {0,0,-1,1};
    	
    	result[startx][starty]= 0;
    	visited[startx][starty] = true;
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.r;
    		int y = temp.c;
    		int cnt = temp.cnt;
    		for(int dir=0;dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			
    			if( nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
    			if( map[nx][ny] != 1) continue;
    			if( visited[nx][ny] == true) continue;
    			
    			visited[nx][ny] = true;
    			result[nx][ny] = cnt + 1;
    			q.offer(new Node(nx, ny, cnt + 1));
    		}
    	}
    }
    
}
class Node{
	int r;
	int c;
	int cnt;
	public Node(int r, int c, int cnt) {
		this.r=r;
		this.c=c;
		this.cnt = cnt;
	}
}