[백준] 4485 녹색 옷 입은 애가 젤다지? - BFS(너비우선탐색) + 다익스트라(Dijkstra) JAVA

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

코드설명

BFS 혹은 다익스트라를 활용하는 문제입니다.

 

BFS로 푸는것이 더 빠르게 풀 수 있을 것 같아서 BFS로 풀었습니다.

 

유의해야할점들입니다.

1. 이미 방문했을때 뺏긴 루피보다 크거나 같다면, 해당 공간에 방문하지 않습니다. 

아래의 코드에서 처음에 같을때도 방향에 따라 다르게 들어갈 수 있다는 생각으로 < 로 해서 메모리초과가 났었습니다. 생각해보니, BFS 이기에 어디서 들어오든 같은것으로 처리합니다.

if(visited[nx][ny] <= nValue) continue; 
//이미 최적의 거리로 방문한 적이 있다면, 방문해도 최적의 거리가 나오지 못합니다. 
// < 냐 <= 냐 에 따라서 메모리초과 <= 로 처리해야합니다.

2. PriorityQueue를 활용하여 뺏긴 루피가 너무 클경우 애초에 Queue에 들어가지 않도록 처리하여 메모리 초과를 벗어날 수 있습니다.

 

3. "Problem"을 "Probelm" 으로 처리하여 계속해서 오류가 났었습니다.

 

 

 

( BFS가 아닌 우선순위큐를 활용한 다익스트라를 통해서도 해결할 수 있습니다.  )

이 문제같은경우 각 루피의 범위를 간선의 가중치라고 생각하고, 간선의 가중치에 음수값이 없으므로 다익스트라로 진행할 수 있습니다. (음수값이 있을경우 벨만포드 알고리즘을 사용해야 합니다.)

코드

우선순위큐를 활용한 BFS 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int T, N;
	public static int[][] arr;
	public static int answer = Integer.MAX_VALUE;
	public static int idx = 1;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	while(true) {
    		answer = Integer.MAX_VALUE;
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	
        	N = Integer.parseInt(st.nextToken());
        	if( N == 0) {
        		break ;
        	}
        	arr = new int[N][N];
        	
        	for(int i=0;i<N;i++) {
        		st = new StringTokenizer(br.readLine());
        		for(int j=0;j<N;j++) {
        			arr[i][j]= Integer.parseInt(st.nextToken());
        		}
        	}
 
        	simulate();
        	
    	}
    	System.out.println(sb);
    	
    	
    }
    
    public static void simulate() {
    	int[][] visited = new int[N][N];
    	for(int i=0;i<N;i++) {
			Arrays.fill(visited[i], Integer.MAX_VALUE);
    	}
    	
    	PriorityQueue<Node> pq = new PriorityQueue<>(); // 메모리 초과 문제의 주된 원인 중 하나는 큐가 시뮬레이션의 반복 동안 계속 쌓이면서 메모리를 소비하기에 함수 내부에 선언하여 함수 끝날시에 큐 메모리 삭제되도록 처리
    	pq.offer(new Node(0, 0, arr[0][0]));
    	visited[0][0] = arr[0][0];
    	
    	while(!pq.isEmpty()) {
    		Node temp = pq.poll();
    		int x = temp.x;
    		int y = temp.y;
    		int value = temp.value;
    		
//    		if( x == N-1 && y == N-1) {
//    			answer = Math.min(answer, value);
//    		}
    		
    		for(int dir = 0; dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			
    			if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
    			int nValue = value + arr[nx][ny];
    			if(visited[nx][ny] <= nValue) continue; 
                //이미 최적의 거리로 방문한 적이 있다면, 방문해도 최적의 거리가 나오지 못합니다.
                // < 냐 <= 냐 에 따라서 메모리초과 <= 로 처리해야합니다.
 
    			visited[nx][ny] = nValue;
    			pq.offer(new Node(nx, ny, nValue));
    		}
    	}
    	
    	sb.append("Problem ").append(idx++).append(": ").append(visited[N-1][N-1]).append("\n");
    }
}
class Node implements Comparable<Node>{
	int x;
	int y;
	int value;
	public Node(int x, int y, int value) {
		this.x = x;
		this.y = y;
		this.value = value;
	}
	@Override
	public int compareTo(Node other) {
		if(this.value > other.value) {
			return 1;
		}else if(this.value == other.value) {
			return 0;
		}else {
			return -1;
		}
	}
}

 

일반 BFS로 푼 코드입니다. (메모리초과 발생)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int T, N;
	public static int[][] arr;
	public static int answer = Integer.MAX_VALUE;
	public static int idx = 1;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	while(true) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	
        	N = Integer.parseInt(st.nextToken());
        	if( N == 0) {
        		return ;
        	}
        	arr = new int[N][N];
        	
        	for(int i=0;i<N;i++) {
        		st = new StringTokenizer(br.readLine());
        		for(int j=0;j<N;j++) {
        			arr[i][j]= Integer.parseInt(st.nextToken());
        		}
        	}
        	answer = Integer.MAX_VALUE;
        	simulate();
        	
    	}
    	
    	
    }
    
    public static void simulate() {
    	int[][] visited = new int[N][N];
    	for(int i=0;i<N;i++) {
			Arrays.fill(visited[i], Integer.MAX_VALUE);
    	}
    	
    	Queue<Node> q = new LinkedList<>(); // 메모리 초과 문제의 주된 원인 중 하나는 큐가 시뮬레이션의 반복 동안 계속 쌓이면서 메모리를 소비하기에 함수 내부에 선언하여 함수 끝날시에 큐 메모리 삭제되도록 처리
    	q.offer(new Node(0, 0, arr[0][0]));
    	visited[0][0] = arr[0][0];
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		int value = temp.value;
    		
    		if( x == N-1 && y == N-1) {
    			answer = Math.min(answer, value);
    		}
    		
    		for(int dir = 0; dir<4;dir++) {
    			int nx = x + dx[dir];
    			int ny = y + dy[dir];
    			
    			if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
    			int nValue = value + arr[nx][ny];
    			if(visited[nx][ny] < nValue) continue; //이미 최적의 거리로 방문한 적이 있다면, 방문해도 최적의 거리가 나오지 못합니다.
 
    			visited[nx][ny] = nValue;
    			q.offer(new Node(nx, ny, nValue));
    		}
    	}
    	System.out.println("Problem "+idx++ +": "+answer);
    }
}
class Node{
	int x;
	int y;
	int value;
	public Node(int x, int y, int value) {
		this.x = x;
		this.y = y;
		this.value = value;
	}
}