문제
인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(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
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
|
#include<stdio.h>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
char map[1000][1002];
void dfs(int y, int x, int row, int col) {
if (map[y][x] == '0') {
map[y][x] = '2';
for (int i = 0; i < 4; i++) {
int new_y = y + dy[i];
int new_x = x + dx[i];
if (0 <= new_y && new_y < row && 0 <= new_x && new_x < col)dfs(new_y, new_x, row, col);
}
}
}
int main()
{
int m, n, ans = 0;
scanf("%d%d", &m, &n);
getchar();
for (int i = 0; i < m; i++)
fgets(map[i], n + 2, stdin);
for (int j = 0; j < n; j++)
if (map[0][j] == '0')dfs(0, j, m, n);
for (int i = 0; i < n; i++)
if (map[m - 1][i] == '2')ans = 1;
if (ans)printf("YES\n");
else printf("NO\n");
return 0;
}
|
cs |
첫 번째 행에서 dfs를 실행해서 침투할 수 있는 칸은 2로 바꿔준다.
마지막 행에 2가 있으면 침투할 수 있으니까 YES 없다면 NO 를 출력한다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
백준 온라인 저지 (BOJ) 1644 소수의 연속합 (0) | 2020.09.21 |
---|---|
백준 온라인 저지 (BOJ) 1806 부분합 (0) | 2020.09.21 |
백준 온라인 저지 (BOJ) 17427 약수의 합 2 (0) | 2020.09.21 |
백준 온라인 저지 (BOJ) 1527 금민수의 개수 (0) | 2020.09.21 |
백준 온라인 저지 (BOJ) 14716 현수막 (0) | 2020.09.20 |