[BOJ] 1261 알고스팟 Java 풀이

 

 

BOJ 1261번 알고스팟

 

 

이 문제는 2가지 방식으로 시도했다. 먼저 첫 번째 풀이는 백트래킹 DFS 와 DP를 활용해서 한 번 시도했는데, DP를 활용하지 않았을 때는 시간초과가 나다가 DP를 도입하고 나니 틀렸다는 결과를 받게 됐다. 이 풀이에 대해서는 게시판에 BFS를 활용해 풀이한 사람도 있는 것으로 봐서 DFS 접근이 무조건 안되는 것 같지는 않은데 ... 이유를 찾지 못해 게시판에 도움을 요청하고 기다리고 있는 상태이다. (답변이 달리면 여기에 추가할 예정!) 혹시 여기서라도 이유를 아시는 분은 댓글 답변 부탁드립니다!(코드 하단 첨부)

두 번째 풀이는 다익스트라 알고리즘을 활용하는 것이다. 사실 문제를 보고 다익스트라로 풀 수 있겠다는 생각을 떠올리지 못했다. 개념은 대략 알았어도 활용하는 데 익숙치 않은 것이 이유일 것이다. 다익스트라를 떠올리고 나면 문제는 기본적인 다익스트라 알고리즘 구현으로 쉽게 해결할 수 있다. 벽이 세워져 있는 것을 모두 weight로 여기고 (1.1) ~ (N,M)의 최단 경로 길이를 출력하면 된다.

다익스트라 알고리즘 참고: (포스팅 예정)

 

package exhaustiveSearch;

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

public class P1261 {

	static int N, M;
	static int map[][];
	static int dist[][];
	static PriorityQueue<Place> pq;
	static int dx[] = {1, -1, 0, 0};
	static int dy[] = {0, 0, -1, 1};
	static int result;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[N+1][M+1];
		dist = new int[N+1][M+1];
		
		for(int i = 0; i < dist.length; i++) {
			for(int j = 0; j < dist[i].length; j++) {
				dist[i][j] = Integer.MAX_VALUE;
			}
		}
		
		for(int i = 1; i <= N; i++) {
			String line = br.readLine();
			for(int j = 1; j <= M; j++) {
				map[i][j] = line.charAt(j-1) - '0';
			}
		}
		
		// Priority Queue 생성
		pq = new PriorityQueue<>();
		bfs();
		System.out.println(result);
		
		
	}
	
	private static void bfs() {
		// 첫 번째 시작 값 
		pq.add(new Place(1, 1, 0));
		dist[1][1] = 0;
		
		while(!pq.isEmpty()) {
			Place now = pq.poll();
			
			// 목적지에 도착했는가
			if(now.x == N && now.y == M) {
				result = now.cost;
				return;
			}
			
			for(int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];
				
				// map의 범위 안에 존재하면
				if(0 < nx && nx <= N && 0 < ny && ny <= M) {
					// 지금까지 찾은 최소 weight 경로보다 작으면 변경 후 이동
					if(dist[nx][ny] > dist[now.x][now.y] + map[nx][ny]) {
						dist[nx][ny] = dist[now.x][now.y] + map[nx][ny];
						pq.add(new Place(nx, ny, dist[nx][ny]));
					}
				}
			}
		}
	}

}

class Place implements Comparable<Place>{
	int x, y, cost;

	public Place(int x, int y, int cost) {
		this.x = x;
		this.y = y;
		this.cost = cost;
	}

	@Override
	public int compareTo(Place o) {
		if(this.cost < o.cost) return -1; 
		return 1;
	}
}

 

풀이가 전형적인 다익스트라 알고리즘과 동일하므로, 별도 설명을 첨부하지는 않는다.

 

첫 번째로 시도했던 DFS 백트래킹 & DP 풀이 코드

package exhaustiveSearch;

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

public class P1261_DFS_DP {
	static int miro[][];
	static boolean visited[][];
	static int ans;
	static int N, M;
	static int dx[] = {1, -1, 0, 0};
	static int dy[] = {0, 0, 1, -1};
	static int dp[][];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		miro = new int[N+1][M+1];
		visited = new boolean[N+1][M+1];
		dp = new int[N+1][M+1];
		
		for(int i = 1; i<= N; i++) {
			String line = br.readLine();
			for(int j = 1; j<=M; j++) {
				miro[i][j] = line.charAt(j-1) - '0';
			}
		}
		
        // 초기값 설정 -> 각 값은 100을 넘을 수 없음
		for(int i = 1; i<= N; i++) {
			for(int j = 1; j<=M; j++) {
				dp[i][j] = 101;
			}
		}
		
		ans = 101;
		dfs(1, 1, 0, visited);
		System.out.println(ans);
	}
	
	static void dfs(int row, int col, int cnt, boolean[][] visited) {
    	// 도착지에 도착한 경우
		if(row >= N && col>= M) {
			ans = Math.min(ans, cnt);
			return;
		}
		
        // 이미 방문한 자리인데 오면서 걸린 cnt가 이전 방문보다 같거나 큰 경우 탐색X
		if(dp[row][col] <= cnt) {
			return;
		}
		
		visited[row][col] = true;
		dp[row][col] = cnt;
		
		for(int i = 0; i< 4; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			if(0 < nx && nx <= N && 0 < ny && ny <= M) {
            	// 방문하지 않은 곳이라면 
				if(!visited[nx][ny]) {
                	// 벽이라면 cnt 증가
					if(miro[nx][ny] == 1) {
						dfs(nx, ny, cnt+1, visited);
					}else {
                    	// 벽이 아니면 cnt 증가하지 않은채로 진행
						dfs(nx, ny, cnt, visited);
					}
				}
			}
		}
		visited[row][col] = false;
	}
}