728x90
⬛ 백준 13565번. 침투 - BFS& DFS 풀이
https://www.acmicpc.net/problem/13565
문제
인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다.
김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하시오.
예를 들어, Figure 1(a) 에서는 바깥쪽에서 공급된 전류가 안쪽까지 침투하지만, Figure 1(b)에서는 그렇지 못한다.
입력
첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않는 검은색 격자임을 뜻한다.
출력
바깥에서 흘려준 전류가 안쪽까지 잘 전달되면 YES를 출력한다.
그렇지 않으면 NO를 출력한다.
💚나의 풀이
1) BFS 풀이
- 우선 바깥쪽은 0행 위치에서 값이 0인 부분이 될 것이고, 안쪽은 N-1행 위치에서 값이 0인 부분이 될 것이다.
- 이 문제는 0행쪽에 보낸 전류가 쭉 연결이 되어서 안쪽인 N-1행까지 잘 전달이 되었는지 확인하는 문제였다.
- 우선은 BFS로 문제를 풀었다.
- 시작하는 위치는 0행에서 값이 0인 곳을 찾아 BFS를 반복하여 호출하는데 그 호출한 값의 리턴이 true 즉, 밑바닥에 한 번이라도 닿는 게 있으면 YES를 , 밑바닥에 한 번도 닿지 못해서 false가 리턴 되었으면 NO를 출력하면 되는 문제이다.
package to_0908_7;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*백준 13565번 침투 - BFS & DFS 풀이 */
public class Main {
static int N, M;
static int[][] map;
static boolean[][] visited;
//4방향
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
//BFS
static boolean BFS(int x, int y) {
Queue<int[]> Q= new LinkedList<>();
visited[x][y] = true;
Q.offer(new int[] {x, y});
while(!Q.isEmpty()) {
int[] cur = Q.poll();
//만약 여기서 뽑은 애가 N-1이 된다면 밑마닥까지 닿은 거니까 true 리턴시킴
if(cur[0] == N-1) return true;
for(int k= 0; k<4; k++) {
int nx = cur[0] + dx[k];
int ny = cur[1] + dy[k];
if(nx <0 || ny <0 || nx >= N || ny>=M) continue;
//전류 통하는 0 이 존재한다면 계속 넘비 탐색
if(!visited[nx][ny] && map[nx][ny] == 0) {
Q.offer(new int[] {nx, ny});
visited[nx][ny] = true;
}
}
}
return false;
}
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
N = kb.nextInt();
M = kb.nextInt();
map = new int[N][M];
for(int i=0; i<N; i++) {
String tmp = kb.next();
for(int j=0; j<M; j++) {
map[i][j] = Character.getNumericValue(tmp.charAt(j));
}
}
visited= new boolean[N][M];
boolean flag = false;
for(int i=0; i<M; i++) {
if(map[0][i] == 0) {//즉 바깥 라인에서 전류 흐를 수 있는 흰색일 경우
if(BFS(0, i)) {
flag = true;//하나라도 밑바닥까지 전달되는 게 있다면 true
}
}
}
if(!flag) {
System.out.println("NO");
}else {
System.out.println("YES");
}
}
}
2) DFS 풀이
- 여기서는 반환을 따로 해주지 않고 정적 변수로 flag를 false로 초기화해둔 뒤 0행의 값이 0인 곳에서 DFS를 모두 호출해주다가 x값이 N-1행에 닿는 곳이 생기게 되면 flag = true로 갱신하도록 해두었다.
- 결과적으로 DFS를 호출해서 안쪽 N-1행까지 쭉 뻗을 수 있다면 YES , 아니라면 NO를 출력하도록 문제를 풀었다.
import java.util.*;
/*백준 13565번 침투 - BFS & DFS 풀이 */
public class Main {
static int N, M;
static int[][] map;
static boolean[][] visited;
static boolean flag = false;
//4방향
static int[] dx = {0, 0, 1, -1};
static int[] dy = {1, -1, 0, 0};
//DFS
static void DFS(int x, int y) {
if(x == N-1) {//깊이 호출하다가 x행이 N-1밑바닥 행이 된다면
flag = true;//여기서 true 리턴하면 되고
}
visited[x][y] = true;
for(int k =0; k<4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if(nx <0 || ny <0 || nx >= N || ny>=M) continue;
if(!visited[nx][ny] && map[nx][ny] == 0) {
DFS(nx, ny);
}
}
}
//실행 메인
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner kb= new Scanner(System.in);
N = kb.nextInt();
M = kb.nextInt();
map = new int[N][M];
for(int i=0; i<N; i++) {
String tmp = kb.next();
for(int j=0; j<M; j++) {
map[i][j] = Character.getNumericValue(tmp.charAt(j));
}
}
visited= new boolean[N][M];
for(int i=0; i<M; i++) {
if(map[0][i] == 0) {//즉 바깥 라인에서 전류 흐를 수 있는 흰색일 경우
DFS(0, i);//모두 호출해도
}
}
if(!flag) {
System.out.println("NO");
}else {
System.out.println("YES");
}
}
}
728x90
'코딩 테스트 [준비] > [문풀] Baekjoon_백준 문풀_조지기' 카테고리의 다른 글
백준 | 14621번. 나만 안되는 연애 -최소비용 신장 트리 (1) | 2023.09.11 |
---|---|
백준 | 14716번. 현수막 - DFS & BFS 풀이 (0) | 2023.09.11 |
백준 | 16194번. 카드 구매하기 2 - DP 문제 (0) | 2023.09.08 |
백준 | 2156번. 포도주 시식 - DP 문제 (0) | 2023.09.08 |
백준 | 21924번. 도시 건설 - 최소비용 신장 트리 (0) | 2023.09.07 |