728x90
반응형
[백준] 13565 침투 cpp 풀이
알고리즘: 그래프 이론, 그래프 탐색, 너비우선탐색(bfs), 깊이우선탐색(dfs)
https://www.acmicpc.net/problem/13565
문제 요약
- 2차원 격자가 주어지고, 각 격자는 0(전류 흐름)과 1(전류 차단)로 구성되어있다.
- 각 전류는 상하좌우로 이동할 수 있다.
- 이 때, 격자의 위쪽(outer side)에서 아래쪽(inner side) 까지 전류가 올 수 있는지 YES/NO를 출력해주면 된다.
풀이 정리
- 완전 기본적인 dfs 문제였다. M*N 격자 안에 있고 아직 방문하지 않은 점이면서 전류가 흐를 수 있는 0의 칸이라면 dfs로 더 탐색해주었다.
- 상하좌우 4방향에 dx와 dy배열을 이용했다.
- 격자의 맨 위(행=0)인 지점에서 모두 시작했고, 마지막 행(M-1)번째에 0이 하나라도 있으면 전류가 다 흘렀다고 판단했다.
C++ 코드
#include <iostream>
#include <vector>
using namespace std;
int N, M;
int arr[1001][1001];
int visited[1001][1001];
int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
void dfs(int y, int x){
visited[y][x] = 1;
for(int i=0; i<4; i++){
int ny = y+dy[i]; int nx = x+dx[i];
if(ny<0 || ny>=M || nx<0 || nx >=N) continue;
if(visited[ny][nx] == 0 && arr[ny][nx] == 0) dfs(ny, nx);
}
}
int main(){
cin >> M >> N;
for(int i=0; i<M; i++){
for(int j=0; j<N; j++){
char c; cin >> c;
arr[i][j] = c-'0';
}
}
for(int j=0; j<N; j++){
dfs(0, j);
}
bool cango = false;
for(int j=0; j<N; j++){
if(visited[M-1][j] == 1){
cout << "YES\n";
return 0;
}
}
cout << "NO\n";
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[cpp 알고리즘] 백준 15721 번데기 (0) | 2024.08.06 |
---|---|
[cpp 알고리즘] 백준 1080 행렬 (1) | 2024.07.22 |
[cpp 알고리즘] 백준 2422 한윤정이 이탈리에아 가서 아이스크림을 사먹는데 (0) | 2024.07.18 |
[cpp 알고리즘] 백준 20152 Game Addiction (0) | 2024.07.15 |
[cpp 알고리즘] 백준 19844 단어 개수 세기 (1) | 2024.07.15 |