[백준] 10709 기상캐스터 - BFS(너비우선탐색) JAVA

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

코드설명

너비우선탐색(BFS)를 활용합니다.

 

1. BFS 시작 전에 모든 위치를 -1로 초기화한다.
2. BFS를 수행하면서 Node의 time 값을 갱신한다.
3. 만약 BFS가 모두 수행되면 중단한다.
4. BFS가 중단되는 조건은 col 값이 W와 같거나 커지면 더 이상 큐에 삽입하지 않는다.

구름은 동쪽방향으로만 움직이므로, 만약 이미 구름이 있던 흔적이 있다면 Queue에 넣지 않아서 연산시간을 줄일 수 있습니다.

코드

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
 
//1. BFS 시작 전에 모든 위치는 0 -1로 두고 시작한다.
//2. BFS 를 돌며 Node의 time값으로 갱신한다.
//3. 만약, BFS 가 모두 사용되면 중단된다.
//4. BFS가 중단되는 조건은 col, 문제에서는 W보다 col값이 같거나 커지면 더 이상 큐에 삽입하지 않는다.
 
public class Main {
	public static int N, H, W;
	public static int answer = 0;
	public static char[][] map;
	public static int[][] visited;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		map = new char[H][W];
		visited = new int[H][W];
		
		for(int i=0;i<H;i++) {
			for(int j=0;j<W;j++) {
				visited[i][j] = -1;
//				System.out.print(" "+visited[i][j]);
			}
//			System.out.println();
		}
//		System.out.println();
		
		for(int i=0;i<H;i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			
			for(int j=0;j<W;j++) {
				map[i][j] = str.charAt(j);
//				System.out.print(" "+map[i][j]);
			}
//			System.out.println();
		}
//		System.out.println();
		
		BFS();
		for(int i=0;i<H;i++) {
			for(int j=0;j<W;j++) {
				System.out.print(visited[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public static void BFS() {
		int[] dx = {0};
		int[] dy = {1};
		Queue<Node> q = new LinkedList<>();
		for(int i=0;i<H;i++) {
			for(int j=0;j<W;j++) {
				if(map[i][j] == 'c') {
					q.offer(new Node(i, j, 0));
					visited[i][j] = 0;
				}
			}
		}
		
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			for(int dir = 0; dir < 1; dir++) {
				int nr = temp.r + dx[dir];
				int nc = temp.c + dy[dir];
				int ntime = temp.time + 1;
				if(nr >= H || nr < 0 || nc >= W || nc < 0) continue; //범위 넘어간다면,
				if(visited[nr][nc] != -1) continue; //이미 지나간곳임.
				
				visited[nr][nc] = ntime;
				q.offer(new Node(nr, nc, ntime));
			}
			
		}
		
	}
}
class Node{
	int r;
	int c;
	int time;
	public Node(int r, int c, int time) {
		this.r = r;
		this.c = c;
		this.time = time;
	}
}