[백준] code.plus(BFS,JAVA)1261번, 알고스팟

문제 링크

1261번: 알고스팟

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에서 BFS를 통하여 문제를 해결하였습니다.

 

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

 

위 문제는 출발지점에서 목적지점까지 가는 벽을 최소한 부수는 최단경로를 구하는 문제이기 때문에 최단경로 알고리즘을 사용하였습니다.

 

최단경로는 시작 정점에서 목표 정점까지 최소의 비용으로 갈 수 있는 경로를 구하는 것입니다.

최단 경로를 구하는 알고리즘은 대표적으로 3개가 존재합니다.

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

3. 플로이드 워셜 알고리즘

 

3가지 알고리즘은 문제를 해결할 때 사용하는 알고리즘만 설명하도록 하겠습니다.

최단 경로에서 가중치(비용)이 양수이고 단일 - 출발, 단일 - 도착이면 다익스트라 알고리즘으로 구현합니다.

다익스트라 알고리즘이란?

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

1. 출발 정점에서 인접한 정점으로 이동합니다.

2. 인접한 정점에서 가장 적은 가중치(거리)의 정점을 먼저 탐색합니다.

3. 이동을 할 때마다 이동한 거리가 현재 저장된 거리보다 작으면 변경합니다.

4. 위 과정을 반복이 끝나면 출발 정점에서 각 정점에 도착하는 최소 거리을 구할 수 있습니다.

 

글로는 잘 설명하지 못한 것 같아서 아래에 예제 문제를 풀면서 어떻게 진행되는지 자세히 보여드리겠습니다.

 

더 자세한 내용은 아래 링크를 통해 확인해주시기 바랍니다.

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 미로에서 시작하는 지점은(1,1)이며 목표지점은 (N,M)입니다.

2. 미로에 이동하는 방법은 상,하,좌,우로 이동이 가능하며 벽을 부술수 있습니다.

3. 벽이 존재하면 1, 존재하지 않으면 0으로 표현합니다.

4. 벽을 최소한 부수면서 목표지점에 도달할 때 벽을 부순 횟수를 결과로 출력해야 합니다.

 

※저는 프로그래밍되기 쉽게 시작지점(0,0), 목표지점(N-1,M-1)로 설정하고 알고리즘을 작성하였습니다.

 

사용되는 배열

visited[i][j] : (i,j)위치를 방문했는지 확인하는 배열입니다.

 

maze[][] : 미로의 형태를 저장하는 배열입니다.

 

dx[] : 상,하,좌,우 이동할 때 x값의 변경값입니다.

 

dy[] : 상,하,좌,우 이동할 때 y값의 변경값입니다.

 

다익스트라 탐색을 통해 가장 먼저 목표지점에 도착했을 때가 벽을 최소로 부순 횟수입니다.

 

예제입력2으로 다익스트라가 진행되는 과정을 보여드리겠습니다.

N = 4, M = 2

초기 미로

현재 위치 : (0, 0)

0	0	0	1
1	0	0	0

상하좌우 이동

0	0	0	1
1	0	0	0

 

다익스트라 알고리즘의 우선순위로 벽을 부순 횟수로 지정할 것이므로 (0,1)을 먼저 상하좌우 탐색합니다.

 

현재위치 : (0,1)

상하좌우 이동

0	0	0	1
1	0	0	0

(0,2)와 (1,1)은 벽을 부순횟수가 0으로 동일하지만 상하좌우순으로 탐색하기 때문에 (1,1)에서 먼저 상하좌우 탐색합니다.

 

현재위치 : (1,1)

상하좌우 이동

0	0	0	1
1	0	0	0

 

현재위치 : (0, 2)

상하좌우 이동

0	0	0	1
1	0	0	0

(0,3)에는 벽을 1개 부수었기 때문에 (1,2)가 부순 횟수가 적기 때문에 (1,2)를 먼저 탐색한다.

 

현재위치 : (1, 2)

상하좌우 이동

0	0	0	1
1	0	0	0

 

목적지 (N-1,M-1)이 먼저 도착하였기 때문에 벽을 부순 횟수는 0입니다.

 

결과로 0이 출력됩니다.

 

진행되는 경로를 표로 만들어보면

0(→)	0(↓)	0	1
1	0(→)	0(→)	0(도착)

 

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 N,M과 미로에 정보를 저장합니다.

2. 다익스트라 알고리즘을 이용하여 상하좌우로 탐색하였습니다.

3. 다익스트라에서 벽을 적게 부순 방향을 우선으로 하였습니다.

4. 다익스트라에 결과로 얻은 벽을 부순 최소 횟수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 N,M을 나누었습니다.
• 다익스트라를 이용하여 벽을 최소 부수는 최단경로를 구하는 bfs함수를 사용하였습니다.
• BufferedWriter에 bfs를 통해 얻은 벽을 부순 최소 횟수를 저장하였습니다.
• BufferedWriter에 저장된 값을 결과로 출력하였습니다.

• bfs 함수는 BFS를 이용하여 다익스트라 알고리즘을 구현하였습니다.
• bfs함수는 우선순위 큐를 사용하여 벽을 부순 최소 횟수의 최단 경로를 구하였습니다.
• bfs함수는 dx[], dy[]를 이용하여 상하좌우로 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	//다익스트라에 사용하는 우선순위 큐에 생성자
	static class move{
		int x,y, count;		//x좌표, y좌표, 벽을 부순 횟수
		public int getX() {
			return x;
		}
		public int getY() {
			return y;
		}

		public int getCount() {
			return count;
		}

		public move(int x,int y, int count) {
			this.x = x;
			this.y = y;
			this.count = count;
		}
	}
	static int N,M;
	static int[][] maze;		//미로값 저장 배열
	static int[] dx = {-1, 1 , 0, 0};	//상하좌우 x값 변경 배열
	static int[] dy = {0, 0, -1, 1};	//상하좌우 y값 변경 배열
	static boolean[][] visited;		//해당 미로 방문하였는지 확인하는 배열
	public static void main(String[] arg) 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());
		maze = new int[M][N];
		visited = new boolean[M][N];
		for(int i=0;i<M;i++) {
			String value = br.readLine();
			for(int j=0;j<N;j++) {
				maze[i][j] = Character.getNumericValue(value.charAt(j));
			}
		}
		int result = bfs();		//다익스트라 알고리즘을 통해 벽을 부순 최소횟수 저장
		bw.write(result + "\n");	//벽을 부순 최소 횟수 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//다익스트라 알고리즘을 통해 벽을 최소로 부수는 최단경로 구하는 함수
	static int bfs() {
    		//벽을 부순 횟수에 따라 우선순위를 주어지는 큐
		PriorityQueue<move> queue = new PriorityQueue<move>(new Comparator<move>() {
			@Override
			public int compare(move o1, move o2) {
				return o1.count-o2.count;
			}
		});
		queue.add(new move(0,0,0));		//출발 지점 저장
		visited[0][0] = true;		//출발지점 탐색 완료
		while(!queue.isEmpty()) {
			move temp = queue.poll();
			int x = temp.getX();
			int y = temp.getY();
			int count = temp.getCount();
			if(x==M-1 && y==N-1) {		//목표 지점 도달시
				return count;
			}
			for(int i=0;i<dx.length;i++) {
				int tempX = x + dx[i];		//상하좌우 이동시 x값
				int tempY = y + dy[i];		//상하좌우 이동시 y값
				if(tempX>=0 && tempY>=0 && tempX<M && tempY<N && !visited[tempX][tempY]) {
					visited[tempX][tempY] = true;
					if(maze[tempX][tempY]==1) 	//벽을 부수고 이동할 때
						queue.add(new move(tempX,tempY,count+1));				
					else		//벽을 부수지 않고 이동할 때
						queue.add(new move(tempX,tempY,count));
				}
			}
		}
		return 0;
	}
}