G4485. 녹색옷을 입은 애가 젤다지?

문제

제출 코드

1. 1차 시도 : DP

   초반에 DP로 접근했다가 예제 하나가 안맞아서 계속 고치면서 시간 날렸다.

   이 문제는 사방으로 접근할 수 있기에, DP와 맞지 않는 문제였다. 저번에도 이와같은 실수를 했었으니 유의하자.

   • DP 풀이 (오답 코드)

     package gold;
     
     import java.io.BufferedReader;
     import java.io.IOException;
     import java.io.InputStreamReader;
     import java.util.Arrays;
     import java.util.StringTokenizer;
     
     public class G4485_greenZelda {
     
     	public static void main(String[] args) throws NumberFormatException, IOException {
     		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     		int T = 1;
     		while(true) {
     			int N = Integer.parseInt(br.readLine());
     			if(N==0) break;
     			int[][] map = new int[N][N];
     			int[][] dp = new int[N][N];
     			for(int  i=0; i<N; i++) {
     				StringTokenizer st = new StringTokenizer(br.readLine());
     				for(int j=0; j<N; j++) map[i][j] = Integer.parseInt(st.nextToken());
     			}
     			dp[0][0] = map[0][0];
     			for(int i=0; i<N; i++) {
     				for(int j=0; j<N; j++) {
     					if(i==0 && j==0) continue;
     					if(i-1<0) dp[i][j] = dp[i][j-1] + map[i][j];
     					else if(j-1<0) dp[i][j] = dp[i-1][j] + map[i][j];
     					else dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + map[i][j];
     				}
     //				System.out.println(Arrays.toString(dp[i]));
     			}
     			System.out.println("Problem " + T++ + ": " + dp[N-1][N-1]);
     		}
     	}
     
     }
     

1. 2차 시도 : DFS

   시간초과 났다. 분명 풀 수 있는 방법이라고는 했지만, 교수님이 이 문제는 DFS로 풀기 좋지 않으니 풀지 말라고 하셔서 과감히 포기

   • DFS 풀이 (시간초과)

     package gold;
     
     import java.io.BufferedReader;
     import java.io.IOException;
     import java.io.InputStreamReader;
     import java.util.LinkedList;
     import java.util.Queue;
     import java.util.StringTokenizer;
     
     public class G4485_greenZelda {
     	static int N, result;
     	static int[] di = {-1, 0, 1, 0};
     	static int[] dj = {0, 1, 0, -1};
     	static int[][] map;
     	static int[][] visit;
     
     	// dfs로 풀었더니 시간초과 났다.
     	static void dfs(int i, int j, int w) {
     		if(result <= w) return;
     		if(i==N-1 && j==N-1) {
     			result = w;
     			return;
     		}
     		visit[i][j] = 1;
     		for(int d=0; d<4; d++) {
     			int ni = i + di[d];
     			int nj = j + dj[d];
     			if(ni>=0 && ni<N && nj>=0 && nj<N && visit[ni][nj]==0) {
     				dfs(ni, nj, w+map[ni][nj]);
     				visit[ni][nj] = 0;
     			}
     		}
     	}
     
     	public static void main(String[] args) throws NumberFormatException, IOException {
     		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     		int T = 1;
     		while(true) {
     			N = Integer.parseInt(br.readLine());
     			if(N==0) break;
     			map = new int[N][N];
     			visit = new int[N][N];
     			for(int  i=0; i<N; i++) {
     				StringTokenizer st = new StringTokenizer(br.readLine());
     				for(int j=0; j<N; j++) map[i][j] = Integer.parseInt(st.nextToken());
     			}
     			result = Integer.MAX_VALUE;
     			dfs(0, 0, map[0][0]);
     			System.out.println("Problem " + T++ + ": " + result);
     		}
     	}
     
     }
     

1. 3차 시도 : BFS

   혼자서 풀어보다가 가중치를 어떻게 넘겨줘야 할지 막혀서 멈췄었는데, 교수님 풀이를 보고 알게되었다. visit 배열을 boolean이 아닌 int로 선언해서, 그 안에 가중치를 저장하면 visit여부와 가중치 정보를 모두 저장할 수 있었더라.

   • BFS 풀이 (성공)

     package gold;
     
     // DP로 풀었더니 망했고, DFS로 풀었을때 시간초과 난 문제.
     import java.io.BufferedReader;
     import java.io.IOException;
     import java.io.InputStreamReader;
     import java.util.Arrays;
     import java.util.LinkedList;
     import java.util.Queue;
     import java.util.StringTokenizer;
     
     public class G4485_greenZelda {
     	static int N;
     	static int[] di = {-1, 0, 1, 0};
     	static int[] dj = {0, 1, 0, -1};
     	static int[][] map;
     	static int[][] visit; // 여기다가 가중치를 더하는 방법이 있었다
     
     	static class Node{
     		int i, j, w;
     		Node(int i, int j){
     			this.i = i;
     			this.j = j;
     		}
     	}
     
     	static void bfs() {
     		Queue<Node> queue = new LinkedList<>();
     		queue.add(new Node(0, 0));
     		visit[0][0] = map[0][0];
     
     		while(!queue.isEmpty()) {
     			int size = queue.size();
     
     			for(int i=0; i<size; i++) {
     				Node now = queue.poll();
     				for(int d=0; d<4; d++) {
     					int ni = now.i + di[d];
     					int nj = now.j + dj[d];
     					if(ni<0 || ni>=N || nj<0 || nj>=N || (visit[ni][nj]!=-1 &&
     							visit[ni][nj]<=visit[now.i][now.j]+map[ni][nj])) continue;
     					queue.add(new Node(ni, nj));
     					visit[ni][nj] = visit[now.i][now.j] + map[ni][nj];
     				}
     
     			}
     		}
     	}
     
     	public static void main(String[] args) throws NumberFormatException, IOException {
     		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     		int T = 1;
     		while(true) {
     			N = Integer.parseInt(br.readLine());
     			if(N==0) break;
     			map = new int[N][N];
     			visit = new int[N][N];
     
     			for(int  i=0; i<N; i++) {
     				Arrays.fill(visit[i], -1);
     				StringTokenizer st = new StringTokenizer(br.readLine());
     				for(int j=0; j<N; j++) map[i][j] = Integer.parseInt(st.nextToken());
     			}
     			bfs();
     
     			System.out.println("Problem " + T++ + ": " + visit[N-1][N-1]);
     		}
     	}
     
     }