[백준 1981] 배열에서 이동(Java)

1. 문제

www.acmicpc.net/problem/1981

2. 풀이

• 투포인터를 활용해 풀었다.

3. 코드

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static int[][]map;
    static boolean[][] visited;
    static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       // br = new BufferedReader(new StringReader(src));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        map = new int[n][n];

        for(int i =0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j =0; j<n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                max = Math.max(map[i][j], max);
                min = Math.min(map[i][j], min);
            }
        }
        int result = max-min;
        int until = max;
        max = map[0][0];
        while(min<=map[0][0] && max<=until){
            visited = new boolean[n][n];
            if(dfs(0,0)){
                result = Math.min(result,max-min);
                min++;
            }else max++;
        }
        System.out.println(result);
    }
    static boolean dfs(int r, int c){
        if(r==n-1 && c==n-1) return true;
        visited[r][c] = true;
        for(int d=0; d<4; d++){
            int newR = r+dir[d][0];
            int newC = c+dir[d][1];
            if(isRange(newR,newC) && !visited[newR][newC]){
                if(map[newR][newC]>=min &&map[newR][newC]<=max){
                    if(dfs(newR,newC)) return true;
                }
            }
        }
        return false;
    }
    static boolean isRange(int r, int c){
        return r>=0 && c>=0 && n>r && n>c;
    }
    static String src="5\n" +
            "1 1 3 6 8\n" +
            "1 2 2 5 5\n" +
            "4 4 0 3 3\n" +
            "8 0 2 3 4\n" +
            "4 3 0 2 1";
}

반응형