Coding Test - cpp/DFS
[백준 13565: 침투] - C++
에드윈H
2021. 2. 1. 17:43
13565번: 침투
첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않
www.acmicpc.net
#include<iostream>
using namespace std;
int map[1001][1001];
int chk[1001][1001];
int N, M;
int dir[4][2] = {
{-1,0}
,{0,1}
,{1,0}
,{0,-1}
};
bool bIsFind;
void D(int _x, int _y)
{
if (_x == N-1)
{
bIsFind = true;
return;
}
for (int i = 0; i < 4; i++)
{
int nextX = dir[i][0] + _x;
int nextY = dir[i][1] + _y;
if (nextX < 0 || nextY < 0 || N <= nextX || M <= nextY)
continue;
if (chk[nextX][nextY] == 0 && map[nextX][nextY] == 0)
{
chk[nextX][nextY] = 1;
D(nextX,nextY);
}
}
}
int main()
{
cin >> N >> M;
string input;
for (int i = 0; i < N; i++)
{
cin >> input;
for (int j = 0; j < M; j++)
{
map[i][j] = input[j] - '0';
}
}
for (int i = 0; i < M; i++) {
if (map[0][i] == 0) {
chk[0][i] = 1;
D(0, i);
}
}
if (bIsFind)
{
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
return 0;
}