주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.
자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.
출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.
시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.
출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.
DFS
깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전
깊이 우선 탐색의 애니메이션 예시 깊이 우선 탐색( - 優先探索, 영어: depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작
ko.wikipedia.org
BFS
너비 우선 탐색 - 위키백과, 우리 모두의 백과사전
ko.wikipedia.org
이 문제에 핵심은
1. 맵에는 이동가능한 0과 벽으로 막힌 1이 존재합니다.
2. 최대 1개의 벽을 부술 수 있습니다.
3. 목적지까지의 최단 거리를 구해야한다.
저는 BFS(너비우선탐색)을 이용하여 문제를 해결하였습니다.
(0,0)에서부터 상, 하, 좌, 우로 탐색을 진행하여 처음 목적지에 도착했을 때가 최단 거리입니다.
상, 하, 좌, 우로 탐색하기 위해 dx[]와 dy[]를 사용하였습니다.
dx[] = {-1, 1, 0, 0}
dy[] = {0, 0, -1, 1}
벽을 최대 1개까지 부술 수 있기 때문에 벽을 부술 때와 부수지 않았을 때를 따로 구분해서 check를 만들었습니다.
check[][][]를 3차원배열으로 만들어서 설정하였습니다.
check[][][0]일 때 벽을 부수지 않았을 때 탐색한 지점
check[][][1]일 때 벽을 1개 부수고 난 뒤 탐색한 지점
check배열을 통해서 맵에 해당 지점을 탐색했는지를 확인하였습니다.
Queue에서 사용할 생성자 coordinate를 만들었으며
x = x좌표
y = y좌표
distance = 이동 거리
crack = 벽을 부순 여부
예제 입력1을 BFS로 탐색을 하는 과정을 보여드리겠습니다.
| 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 |
1. (0,0)에서 상,하,좌,우로 탐색을 진행합니다.
상, 좌는 맵에 범위를 벗어나기 때문에 우, 하만 탐색하면
모두 벽이기 때문에 각각 벽을 부순 것으로 확인한다.
Queue에는 { (1, 0, 2, true), (0, 1, 2, true) }가 저장됩니다.
check에서는 모두 벽을 부순 것으로 check[][][1]에 true로 변경됩니다.
| 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 |
2. 큐에 값을 꺼내서 상, 하, 좌, 우 BFS 탐색 진행
꺼낸 값 = (1, 0, 2, true)
crack가 true이기 때문에 더 이상 벽을 부술 수 없습니다.
(1,0)에서 상, 하, 좌, 우로 이동가능한 곳이 없기 때문에 탐색 종료
꺼낸 값 = (0, 1, 2, true)
crack가 true이기 때문에 더 이상 벽을 부술 수 없습니다.
(0, 1)에서 상, 하, 좌, 우 중 '우'로 이동가능합니다.
Queue에는 { 0, 2, 3, true) }가 저장됩니다.
check에서는 벽을 부순 것을 증명하는 crack = true이기 때문에 check[][][1]이 true가 됩니다.
위 과정을 반복하여 이동한 값이 목적지에 도착하였을 때
| 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 |
목적지에 도착했을 때 큐에서 꺼낸 distance를 결과로 반환하여 출력하면 됩니다.
예제입력1에서 목적지에 도착했을 때 distance = 15로 15가 결과로 출력되는 것입니다.
문제를 해결한 알고리즘의 과정입니다.
1. 맵에 대한 정보를 저장합니다.
2. BFS(너비 우선 탐색)을 이용하여 상,하,좌,우순으로 탐색을 진행합니다.
3. Queue에 생성자를 사용하여 벽을 부순지 확인합니다.
4. 벽을 부수었다면 check[][][1]을 사용하고 부수지 않았다면 check[][][0]을 사용합니다.
5. 목적지에 도착했을 때 큐에 저장된 distance에 값을 결과로 출력합니다.
- BufferedReader를 사용하여 입력 값을 받았습니다.
- StringTokenizer를 통해 맵에 대한 정보를 저장하였습니다.
- 큐에 사용할 coordinate 생성자를 만들었습니다.
- BFS로 목적 지점 도착하는 최단 거리를 구하는 bfs 함수를 만들었습니다.
- BufferedWriter에 목적지에 도착하면 최단 거리, 목적지 도착못하면 -1를 저장하였습니다.
- BufferedWriter에 저장된 결과값을 출력하였습니다.
- bfs은 check[][][], map[][],dx[],dy[]와 Queue를 통해 지점을 상,하,좌,우를 탐색하였습니다.
- 벽을 부수었다면 check[][][1]을 사용하였으며 부수지 않았다면 check[][][0]을 사용하였습니다.
결과 코드
import java.io.*;
import java.util.*;
public class Main{
//큐에 사용할 생성자
public static class coordinate{
int x,y,distance; //x좌표, y좌표, 이동 거리
boolean crack; //벽을 부순지 확인
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getDistance() {
return distance;
}
public boolean getCrack() {
return crack;
}
public coordinate(int x, int y, int distance,boolean crack) {
this.x = x;
this.y = y;
this.crack = crack;
this.distance = distance;
}
}
public static int N,M;
public static int[][] map; //맵에 대한 정보 저장 배열
public static int[] dx = {-1, 1, 0, 0}; //상,하,좌,우 x 변경값
public static int[] dy = {0, 0, -1, 1}; //상,하,좌,우 y 변경값
public static boolean[][][] check; //벽 부순 유무에 따른 맵 탐색 확인 배열
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력값 처리하는 BufferedReader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//결과값 출력하는 BufferedWriter
//--------입력값 저장 및 배열 초기화--------
StringTokenizer st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
check = new boolean[N][M][2];
for(int i=0;i<N;i++) {
String str = br.readLine();
for(int j=0;j<M;j++) {
map[i][j] = Character.getNumericValue(str.charAt(j));
}
}
int result = bfs(); //함수 실행 및 최단 거리 얻기
bw.write(result + "\n"); //최단 거리 BufferedWriter 저장
bw.flush(); //결과 출력
bw.close();
br.close();
}
//----------BFS 탐색을 통한 최단 거리 구하는 함수------
public static int bfs() {
Queue<coordinate> queue = new LinkedList<coordinate>(); //BFS에 사용될 큐
queue.add(new coordinate(0, 0, 1, false));
check[0][0][0] = true;
while(!queue.isEmpty()) {
int size = queue.size();
for(int i=0;i<size;i++) {
coordinate temp = queue.poll();
int x = temp.getX();
int y = temp.getY();
int distance = temp.getDistance();
boolean crack = temp.getCrack();
if(x==N-1 && y == M-1) { //목적지 도착시 distance 반환
return distance;
}
for(int j=0;j<4;j++) {
int tempX = x + dx[j]; //상,하,좌,우 x값 변경
int tempY = y + dy[j]; //상,하,좌,우 y값 변경
if(tempX>=0 && tempX<N && tempY>=0 && tempY<M) {
if(map[tempX][tempY]==0) {//벽을 부수지 않고 이동가능한 곳
if(!crack && !check[tempX][tempY][0]) {
queue.add(new coordinate(tempX, tempY,
distance+1, false));
//벽 부수지 않아서 check[][][0] 변경
check[tempX][tempY][0] = true;
//벽을 부수었을 때 이동가능한 곳
}else if(crack && !check[tempX][tempY][1]) {
queue.add(new coordinate(tempX, tempY,
distance+1, true));
//벽을 부셔서 check[][][1] 변경
check[tempX][tempY][1] = true;
}
}else {
if(!crack) { //벽을 부수지 않고 벽을 만났을 때
queue.add(new coordinate(tempX, tempY,
distance+1, true));
//벽으로 이동하는 것으로 벽을 부수었기 때문에 check[][][1] 변경
check[tempX][tempY][1] = true;
}
}
}
}
}
}
return -1; //목적지 도착 못했을 경우
}
}'백준' 카테고리의 다른 글
| [백준] code.plus(브루트포스-비트마스크,JAVA)1182번, 부분수열의 합 (0) | 2022.03.30 |
|---|---|
| [백준] code.plus(브루트포스-비트마스크,JAVA)11723번, 집합 (0) | 2022.03.29 |
| [백준] code.plus(브루트포스-순열,JAVA)6603번, 로또 (0) | 2022.03.27 |
| [백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)1697번, 숨바꼭질 (0) | 2022.03.26 |
| [백준] code.plus(브루트포스-순열,JAVA)10971번, 외판원 순회 2 (0) | 2022.03.26 |
댓글