[Java] SWEA 1249 보급로

1249 보급로 문제 링크

#1

package week03;

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

public class SWEA_1249 {
	static int N;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		int dx[] = {0, 1, -1, 0}; // 우하상좌
		int dy[] = {1, 0, 0, -1};
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			
			int[][] map = new int[N][N];
			int[][] result = new int[N][N];
			for(int i=0; i<N; i++) {
				Arrays.fill(result[i], -1);
			}
			String now;
			for(int i=0; i<N; i++) {
				now = br.readLine();
				for(int j=0; j<N; j++) {
					map[i][j] = now.charAt(j) - '0';
				}
			}
			
			result[0][0] = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					for(int a=0; a<2; a++) { // 우하
						if(inArray(i+dx[a], j+dy[a])) {
							if(result[i+dx[a]][j+dy[a]] == -1) result[i+dx[a]][j+dy[a]] = result[i][j] + map[i+dx[a]][j+dy[a]];
							else result[i+dx[a]][j+dy[a]] = Math.min(result[i][j] + map[i+dx[a]][j+dy[a]], result[i+dx[a]][j+dy[a]]);
						}
					}
					for(int a=2; a<4; a++) { // 상좌
						if(inArray(i+dx[a], j+dy[a])) {
							// 상좌는 일단 값이 없을 리가 없어..
							// 기존 값보다 갱신 값이 더 작아
							if(result[i][j] + map[i+dx[a]][j+dy[a]] < result[i+dx[a]][j+dy[a]]) {
								result[i+dx[a]][j+dy[a]] = result[i][j] + map[i+dx[a]][j+dy[a]];
								// 해당 위치부터 다시 탐색
								i = i+dx[a];
								j = j+dy[a];
								continue;
							}
						}
					}
				}
			}
			
			System.out.println(result[N-1][N-1]);
		}
	}
	
	public static boolean inArray(int x, int y) {
		if(x>=0 && x<N && y>=0 && y<N) return true;
		else return false;
	}
}

• 하.. 이렇게 하면 될 줄 알았는데
• i, j를 직접적으로 조작하면 안된대요..
• 생각해보니 for문으로 i,j를 반복 돌릴 때마다 갱신 중인데 저 안에서 갱신한다고 제대로 작동할 리가 없는 것 같기도 하고..
• 아직 반만 이해가 된 거 같긴 하다

#2

package week03;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
 
public class SWEA_1249 {
    static int N;
     
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int dx[] = {0, 1, -1, 0}; // 우하상좌
        int dy[] = {1, 0, 0, -1};
        for(int t=1; t<=T; t++) {
            N = Integer.parseInt(br.readLine());
             
            int[][] map = new int[N][N];
            int[][] result = new int[N][N];
            for(int i=0; i<N; i++) {
                Arrays.fill(result[i], -1);
            }
            String now;
            for(int i=0; i<N; i++) {
                now = br.readLine();
                for(int j=0; j<N; j++) {
                    map[i][j] = now.charAt(j) - '0';
                }
            }
             
            result[0][0] = 0;
            Deque<Point> list = new ArrayDeque<>();
            Point p = new Point(0, 0);
            list.add(p);
            
            while(!list.isEmpty()) {
                p = list.pollFirst();
                for(int a=0; a<4; a++) { // 상하좌우 탐색
                	// 탐색하려는 곳이 배열 범위 안쪽이여야 함
                    if(inArray(p.x+dx[a], p.y+dy[a])) {
                        // 탐색하려는 곳에 처음 진입
                        if(result[p.x+dx[a]][p.y+dy[a]] == -1) {
                        	// 현재 위치의 가중치와 탐색하려는 곳의 가중치를 더해 해당 공간에 넣음
                            result[p.x+dx[a]][p.y+dy[a]] = result[p.x][p.y] + map[p.x+dx[a]][p.y+dy[a]];
                            // 탐색하려는 곳을 탐색 list에 넣음
                            list.add(new Point(p.x+dx[a], p.y+dy[a]));
                        }
                        // 탐색하려는 곳에 이미 진입한 적 있음
                        else {
                        	// 현재 위치의 가중치와 탐색하려는 곳의 가중치의 더한 값  < 탐색했던 기록 값 비교 (최솟값 구하는 중임)
                            if(result[p.x][p.y] + map[p.x+dx[a]][p.y+dy[a]] < result[p.x+dx[a]][p.y+dy[a]]) {
                                // 값 갱신
                            	result[p.x+dx[a]][p.y+dy[a]] = result[p.x][p.y] + map[p.x+dx[a]][p.y+dy[a]];
                                // 값을 갱신 했으니 다시 탐색 필요
                            	list.add(new Point(p.x+dx[a], p.y+dy[a]));
                            }
                        }
                    }
                }
            }
             
            StringBuilder sb = new StringBuilder();
            sb.append("#").append(t).append(" ").append(result[N-1][N-1]);
            System.out.println(sb.toString());
        }
    }
     
    public static boolean inArray(int x, int y) {
        if(x>=0 && x<N && y>=0 && y<N) return true;
        else return false;
    }
}

• 완탐에 메모라이저 사용해서 시간 복잡도를 줄이고 싶었으나..
• 결국 돌고 돌아 완탐과 다를 바 없어졌다..