[백준]13565번, 침투

백준 Q.13656, 침투

문제 :

인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(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를 출력한다.

 

<소스 코드>

import java.util.*;
 
public class Prac {
    static int a,b;
    static int[][] map;
    static boolean answer=false;
    static void going(int pa, int pb){
        map[pa][pb] = 1;//방문
 
        if(pa == a-1)//outside 도착하면
            answer = true; //answer = true
 
        //아래로
        if(pa < a-1 && map[pa+1][pb]==0)
            going(pa+1,pb);
        //왼쪽
        if(pb > 0 && map[pa][pb-1]==0)
            going(pa,pb-1);
        //오른쪽
        if(pb < b-1 && map[pa][pb+1]==0)
            going(pa,pb+1);
        //위
        if(pa > 0 && map[pa-1][pb]==0)
            going(pa-1,pb);
 
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        a = sc.nextInt(); b = sc.nextInt();
        map = new int[a][b];
 
        for(int i = 0; i < a; i++){//입력
            String s = sc.next();
            for(int j = 0; j < b; j++)
                map[i][j] = (int)s.charAt(j)-48;
        }
 
        for(int i = 0; i < b; i++)//b가 0인 부분을 골라 탐색을 시작한다.
            if(map[0][i] == 0)
                going(0,i);
 
        System.out.println(answer ? "YES" : "NO");
    }
}

 

<실행결과>

 

<해법>

1. colum(b)이 0인 부분을 찾아 이동 함수(going)에 넣는다.

2. 이동 함수(going)를 재귀 호출하여 row(a)가 맨 아래에 도착하면 answer = true

 

****이동함수(going(int pa, int pb)) , pa,pb : 현재 위치

map[pa][pb] = 방문표시

if 현재 위치가 outside라면

answer = true;

return;

if 아래로 이동 가능하다면

going(pa+1,pb)

if 왼쪽으로 이동 가능하다면

going(pa,pb-1)

if 오른쪽으로 이동 가능하다면

going(pa,pb+1)

if 위로 이동 가능하다면

going(pa-1,pb)

 

문제 사이트 및 참고 사이트 : https://www.acmicpc.net/problem/13565

※
본 게시물은 개인적인 용도로 작성된 게시물입니다. 이후 포트폴리오로 사용될 정리 자료이니 불펌과 무단도용은 하지 말아주시고 개인 공부 목적으로만 이용해주시기 바랍니다.

※