728x90
https://www.acmicpc.net/problem/13565
🤔 문제 풀이
자주 접했던 그래프 탐색 문제들과 비슷한 문제여서 어렵지 않게 풀어냈다.
그래프 탐색 알고리즘은 BFS를 사용했고 map의 정보들 중
inner side 가 0인 곳과 outer side가 0인 곳을 배열을 생성해 담아두고
이후 각 inner side에서 시작하여 탐색이 끝나면 outer side에 도달했는지 여부를 검사했다.
🚨CODE
import java.io.*;
import java.util.*;
public class Main {
static int n,m;
static int[][] map;
static ArrayList<int[]> outer, inner;
static boolean[][] visit;
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,1,-1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][m];
outer = new ArrayList<>();
inner = new ArrayList<>();
for(int i = 0; i<n; i++) {
String[] mapInfo = br.readLine().split("");
for(int j = 0; j<mapInfo.length; j++) {
int info = Integer.parseInt(mapInfo[j]);
if(i == 0 && info == 0)
outer.add(new int[] {i,j});
if(i == n-1 && info == 0)
inner.add(new int[] {i,j});
map[i][j] = info;
}
}
boolean isPercolate = false;
for(int[] pos : outer) {
visit = new boolean[n][m];
bfs(pos);
isPercolate = checkPercolate();
if(isPercolate) {
System.out.println("YES");
break;
}
}
if(!isPercolate)
System.out.println("NO");
}
public static void bfs(int[] outer) {
Queue<int[]> q = new LinkedList<>();
visit[outer[0]][outer[1]] = true;
q.offer(outer);
while(!q.isEmpty()) {
int[] curPos = q.poll();
int x = curPos[0];
int y = curPos[1];
for(int i = 0; i<4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if(nextX<0 || nextY<0 || nextX >= n || nextY >= m)
continue;
if(visit[nextX][nextY] || map[nextX][nextY] == 1)
continue;
q.offer(new int[] {nextX, nextY});
visit[nextX][nextY] = true;
}
}
}
public static boolean checkPercolate() {
for(int[] innerElement : inner) {
int x = innerElement[0];
int y = innerElement[1];
if(visit[x][y])
return true;
}
return false;
}
}
728x90
반응형
'코딩테스트' 카테고리의 다른 글
[Gold3-JAVA] 백준 2638 - 치즈 (0) | 2024.03.24 |
---|---|
[Silver3-JAVA] 백준 2193 - 이친수 (0) | 2024.03.24 |
[Gold4-JAVA] 백준 1967 - 트리의 지름 (1) | 2024.03.22 |
[JAVA] 백준 11048 - 이동하기 (0) | 2024.03.19 |
[JAVA] 백준 1238 - 파티 (0) | 2024.03.18 |