Notice
Recent Posts
Recent Comments
Link
«   2025/03   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31
Tags
more
Archives
Today
Total
관리 메뉴

끄적끄적

백준[13565] 침투 -그래프 본문

코테준비

백준[13565] 침투 -그래프

alstj_성공 2021. 8. 13. 17:56

출처 : https://www.acmicpc.net/problem/13565

 

침투 

 

1 초 512 MB 3472 1461 1093 44.090%

문제

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

 

 

 

bfs, dfs 두가지 선택지가 있었지만 그냥 dfs로 풀었다.

첫줄 0인 칸부터 시작해서 각 정점에 방문할때마다 visit 배열을 이용하여 방문 표시를 해주고,

맨 밑줄에 도달할시 길을 찾았음을 의미하는 변수인 findPath를 1로 해준 뒤 리턴해주면 된다.

 

'코테준비' 카테고리의 다른 글

프로그래머스 level3 [N으로 표현]  (0) 2021.08.26
백준[1068] 트리 - 그래프  (0) 2021.08.13
백준[1260] DFS와 BFS  (0) 2021.08.13
백준[1890] 점프 - dp  (0) 2021.08.05
백준[15486] 퇴사2 - dp  (0) 2021.08.05