[백준] bfs- 6593번 상범빌딩 (Java)

[백준] bfs- 6593번 상범빌딩 (Java)

반응형

SMALL

접근한 방법

두 개의 노드 간의 거리를 구하는 문제이므로, bfs로 접근해보았다.

증명/ 풀이방법

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다.

시작지점(S가 있는 좌표)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다.

특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 배열에 넣는다.

소스코드 작성 방법

이 문제는 흔히 푸는 2차원 배열 문제에 방향 하나만 더해진 것 뿐이므로,

모든 요소에 하나씩만 더 고려해주면 된다.

빌딩의 크기(l,r,c)를 전역 필드로 선언한다.

시작 지점(sl,sr,sc)과 끝 지점(el,er,ec)을 전역 필드로 선언한다.

빌딩의 정보(building), 방문 여부 및 거리(visited)도 전역 필드로 선언한다.

방향 배열 dl, dr, dc로 동,서,남,북,상,하 움직임을 저장한다.

층, 행, 열의 index를 저장할 수 있는 클래스를 선언한다.

bfs 메소드를 선언하여 아래와 같이 처리해준다.

큐를 초기화 시켜준다.

큐에 맨 처음 좌표의 객체를 넣어준다.

처음 칸도 지나는 것에 포함되므로 visited[sl][sr][sc] = 0 로 처리해주어, 방문 처리 및 거리를 저장한다.

while문으로 큐에 남아있는 게 없을 때까지 탐색을 수행한다. q.poll()로 큐에서 좌표 객체를 꺼내 현재 좌표인 curL, curR, curC 필드에 저장한다. 반복문으로 현재 좌표에서 6방향으로 탐색을 수행한다. 이 때, 다음으로 탐색할 좌표가 탐색할 빌딩의 크기를 벗어나 진행하지 못할 경우 continue로 넘어간다. 빌딩의 값이 #이 아니고 아직 방문하지 않았다면(visited의 좌표가 -1이라면) visited[nextL][nextR][nextC]에 visited[curL][curR][curC] + 1을 저장한다. (현재까지의 거리 + 1) 큐에 다음 좌표의 객체를 넣어준다.

소스코드

package baekjoon.dfs_bfs; import java.io.*; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Q_6593_SangbumBuilding_20210728 { public static int l,r,c; // l : 층 수 | r : 행 | c : 열 public static int sl,sr,sc; public static int el,er,ec; public static char[][][] building; public static int[][][] visited; public static int[] dl = {0, 0, 0, 0, -1, 1}; public static int[] dr = {-1, 0, 1, 0, 0, 0}; public static int[] dc = {0, -1, 0, 1, 0, 0}; public static void bfs(){ Queue q = new LinkedList<>(); q.add(new Pair(sl, sr, sc)); visited[sl][sr][sc] = 0; while (!q.isEmpty()) { Pair cur = q.poll(); int curL = cur.l; int curR = cur.r; int curC = cur.c; for (int i = 0; i < 6; i++) { int nextL = curL + dl[i]; int nextR = curR + dr[i]; int nextC = curC + dc[i]; if (nextL < 0 || nextL >= l || nextR < 0 || nextR >= r || nextC < 0 || nextC >= c) continue; if (building[nextL][nextR][nextC] != '#' && visited[nextL][nextR][nextC] == -1){ q.add(new Pair(nextL, nextR, nextC)); visited[nextL][nextR][nextC] = visited[curL][curR][curC] + 1; } } } } public static void main (String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); while(true){ StringTokenizer st = new StringTokenizer(br.readLine()); l = Integer.parseInt(st.nextToken()); r = Integer.parseInt(st.nextToken()); c = Integer.parseInt(st.nextToken()); if(l == 0 && r == 0 && c == 0) break; building = new char[l][r][c]; visited = new int[l][r][c]; for (int i = 0; i < l; i++) { for (int j = 0; j < r; j++) { String temp = br.readLine(); for (int k = 0; k < c; k++) { building[i][j][k] = temp.charAt(k); visited[i][j][k] = -1; // -1로 초기화 if(building[i][j][k] == 'S'){ sl = i; sr = j; sc = k; } if(building[i][j][k] == 'E'){ el = i; er = j; ec = k; } } } br.readLine(); } bfs(); if(visited[el][er][ec] == -1){ bw.write("Trapped!

"); } else { bw.write("Escaped in "+visited[el][er][ec]+" minute(s).

"); } } br.close(); bw.close(); } public static class Pair{ int l; int r; int c; public Pair(int l, int r, int c){ this.l = l; this.r = r; this.c = c; } } }

반응형

LIST

from http://doongjeol.tistory.com/123 by ccl(A) rewrite - 2021-07-28 10:26:29