[Baekjoon] 13565_침투

Silver II

문제(출처: https://www.acmicpc.net/problem/13565)

---

<  침투 >

 

문제 풀이

 

바깥쪽에서 공급된 전류의 위치를 찾은 후 상하좌우를 탐색하여 bfs를 활용해 주었다.

 

 

 - my solution (Java)

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 _13565_ {
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	static Queue<int[]>queue;
	static boolean flag, visited[][];
	static int m,n, map[][];

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		m=Integer.parseInt(st.nextToken());
		n=Integer.parseInt(st.nextToken());
		map=new int[m][n];
		visited=new boolean[m][n];
		
		queue=new LinkedList<>();
		flag=false;
		
		for(int i=0; i<m; i++) {
			String line=bf.readLine();
			for(int j=0; j<n; j++) {
				map[i][j]=line.charAt(j)-'0';
				if(i==0 && map[i][j]==0) {
					queue.add(new int[] {i,j});
					visited[i][j]=true;
				}
			}
		}
		search();
		if(flag) System.out.println("YES");
		else System.out.println("NO");
	}

	private static void search() {
		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			for(int i=0; i<4; i++) {
				int x=temp[0]+dx[i];
				int y=temp[1]+dy[i];
				if(x>=0 && x<m && y>=0 && y<n) {
					if(map[x][y]==0 && !visited[x][y]) { // 전류 통함
						if(x==m-1) {
							flag=true;
							break;
						}
						visited[x][y]=true;
						queue.add(new int[] {x,y});
					}
				}
			}
			if(flag) break;
		}
	}
}

 

• Main
  • n, m 입력
  • map : 섬유 물질 격자
  • visited: 전류 방문 여부
  • queue: 전류의 위치 저장
  • flag: 전류가 안쪽까지 침투되었는지 확인
  • 섬유 물질 격자 정보를 입력받으면서 가장 바깥쪽에서 전류가 공급된 위치를 찾아 queue에 저장해 준다.
  • search() 함수 호출
  • 전류의 침투 여부(flag)에 따라 정답 출력
• search
  • queue에서 전류의 위치를 꺼내옴
  • 상하좌우로 이동하여 격자 범위 안이며, 전류가 잘 통하는 흰색이고 아직 방문하지 않았다면 queue에 넣어준다. queue에 넣기 전에 안쪽까지 도달했다면 바로 종료해 준다.

---

생각🤔

 

bfs를 활용하여 쉽게 해결할 수 있었다.

 

 

---