백준 13565번 : 침투

 문제

www.acmicpc.net/problem/13565

13565번: 침투

13565 침투

 

 구현 방법

 bfs로 구현하였습니다. 바깥쪽인 위쪽에서 시작하여 안쪽인 아래쪽까지 가야 YES 이므로 입력을 받을 때 높이가 0이고 전류가 잘 통하는 0번일 때 큐에 넣어주었습니다.

flag를 주어 값을 전부 입력 후 bfs를 돌려주어 인접한 위치의 높이가 M줄일 때 flag=true이고 flag가 true일 때 YES, 다 돌았는데도 M줄에 다다르지 못해서 flag=false라면 NO를 출력해주었습니다.

 

 구현 코드

package BOJ.Silver.bfsdfs;

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 BOJ13565_침투 {
	static int R, C;
	static int[][] arr, deltas= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static boolean flag;
	static Queue<move> bfs;
	static class move {
		int r, c;

		public move(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}
	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());
		arr = new int[R][C];
		bfs = new LinkedList<>();
		for (int r=0;r<R;r++) {
			String input = br.readLine();
			for (int c=0;c<C;c++) {
				arr[r][c] = input.charAt(c)-'0';
				if(arr[0][c] == 0) bfs.offer(new move(0, c)); // 0줄일 때 빈칸이라면 큐에 추가
			}
		}
		//입력완료
		bfsL();
		
		if (flag) System.out.println("YES");
		else System.out.println("NO");
	}
	
	static void bfsL() {
		while(!bfs.isEmpty()) {
			move now = bfs.poll();
			for (int d=0;d<4;d++) {
				int nr = now.r+deltas[d][0];
				int nc = now.c+deltas[d][1];
				if (isIn(nr, nc) && arr[nr][nc] == 0) {
					if (nr==R-1) { // 인접한 값의 높이가 M줄일 때
						flag = true;
						break;
					}
					arr[nr][nc] = 1;
					bfs.offer(new move(nr, nc));
				}
			}
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!