[BAEKJOON] 1261번 : 알고스팟 (JAVA)

- 알고리즘 분류 : 다익스트라

- 사용 언어 : JAVA

- 문제 요점

1. 다익스트라를 이용하여 만나는 벽의 최소 수를 구하는 문제

DFS를 이용하여 풀어봤는데, 이 경우 시간초과로 발생했다.

 

- DFS 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	// 상하좌우 이동
	public static int[] amove = {-1, 0, 1, 0};
	public static int[] bmove = {0, 1, 0, -1};
	
	// 무한으로 표현될 변수
	public static final int INF = (int)1e9;
	
	// DFS에서 사용할 결과변수
	public static int result = INF;
	
	// N : 가로크기
	// M : 세로크기
	public static int N,M;
	
	// 맵 변수
	public static int[][] map;
	
	// 방문 체크 변수(DFS)
	public static boolean[][] visited;
	
	// DFS함수 시간초과 발생.
	public static void DFS(int a, int b, int count) {
		// 목적지에 도착 시, result와 비교 후 작으면 갱신
		if(a == M-1 && b == N-1) {
			result = Math.min(result, count);
			return;
		}
		
		// 상하좌우 체크
		for(int i=0; i<4; i++) {
			int tempa = a+amove[i];
			int tempb = b+bmove[i];
			
			// 범위 이상하면 벗어나기
			if(tempa < 0 || tempa>=M || tempb < 0 || tempb>=N) {
				continue;
			}
			
			// 방문 안한 곳이라면
			if(visited[tempa][tempb] == false) {
				// 방문 체크
				visited[tempa][tempb] = true;
				
				// 벽이라면
				if(map[tempa][tempb] == 1) {
					// 카운트 증가
					DFS(tempa, tempb, count+1);
				}
				// 아니면
				else {
					// 카운트 증가 X
					DFS(tempa, tempb, count);
				}
				
				// 백트래킹
				visited[tempa][tempb] = false;
			}
		}
	}  
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		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[M][N];
		visited = new boolean[M][N];
		
		for(int i=0; i<M; i++) {
			String temp = br.readLine();
			String[] tempArr = temp.split("");
			
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(tempArr[j]);
			}
		}
		
		// 다익스트라 알고리즘을 이용하여 최소 비용 구하기
		DFS(0,0,0);
		
		System.out.println(result);
	}

}

 

그리하여 다익스트라로 알고리즘을 바꿔서 다시 도전하니 해결하였다..!

 

- 다익스트라 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	// 상하좌우 이동
	public static int[] amove = {-1, 0, 1, 0};
	public static int[] bmove = {0, 1, 0, -1};
	
	// 무한으로 표현될 변수
	public static final int INF = (int)1e9;
	
	// N : 가로크기
	// M : 세로크기
	public static int N,M;
	
	// 맵 변수
	public static int[][] map;
	
	// 다익스트라 알고리즘 확인. 0,0에서 각 노드까지의 만난 벽의 수
	public static int[][] d;
	
	// 다익스트라 알고리즘
	public static void dijkstra() {
		// 우선순위 큐 이용
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		
		// 최소 비용 배열 갱신
		d[0][0] = 0;
		// 우선순위 큐에 추가
		pq.offer(new Node(0,0,0));
		
		// 큐가 빌때까지
		while(!pq.isEmpty()) {
			// 큐에서 하나 꺼내고
			Node node = pq.poll();
			
			// 상하좌우 확인
			for(int i=0; i<4; i++) {
				int tempa = node.a + amove[i];
				int tempb = node.b + bmove[i];
				int tempBroken = node.broken;
				
				// 범위 벗어나면 무시
				if(tempa < 0 || tempa>=M || tempb < 0 || tempb>=N) {
					continue;
				}
				// 벽이라면 카운트
				if(map[tempa][tempb] == 1) {
					tempBroken++;
				}
				// 최소비용 배열보다 현재 경로의 비용이 더 적을 경우 
				if(d[tempa][tempb] > tempBroken) {
					// 갱신
					d[tempa][tempb] = tempBroken;
					
					// 우선순위 큐에 추가
					pq.offer(new Node(tempa, tempb, tempBroken));
				}
				
				
			}
		}
	}
	
	// 우선순위 큐에서 사용할 노드 클래스 정의
	public static class Node implements Comparable<Node>{
		int a;
		int b;
		int broken;
		
		public Node(int a, int b, int broken) {
			this.a = a;
			this.b = b;
			this.broken = broken;
		}
		
		@Override
		public int compareTo(Node other) {
			if(this.a < other.a) {
				return -1;
			}
			else {
				return 1;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		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[M][N];
		d = new int[M][N];
		for(int i=0; i<M; i++) {
			Arrays.fill(d[i], INF);
		}
		
		for(int i=0; i<M; i++) {
			String temp = br.readLine();
			String[] tempArr = temp.split("");
			
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(tempArr[j]);
			}
		}
		
		// 다익스트라 알고리즘을 이용하여 최소 비용 구하기
		dijkstra();
		
		System.out.println(d[M-1][N-1]);
	}

}