[파이썬, Java] 1981. 배열에서 이동

문제

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.

이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다.

예제 입력 1 

5

1 1 3 6 8

1 2 2 5 5

4 4 0 3 3

8 0 2 3 4

4 3 0 2 1

예제 출력 1 

2

 

 

🐝 나의 풀이

// 참고 : https://comyoung.tistory.com/240
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

import static java.lang.Math.max;
import static java.lang.Math.min;

class Pos{
    int x;
    int y;
    Pos(int x, int y){
        this.x=x;
        this.y=y;
    }
}

class Main{
    static int n;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx={0, 0, -1, 1};
    static int[] dy={-1, 1, 0, 0};

    static boolean bfs(int s, int e){
        Queue<Pos> que=new LinkedList<>();
        que.add(new Pos(0, 0));
        visited=new boolean[n][n];
        visited[0][0]=true;
        while(!que.isEmpty()){
            Pos pos=que.poll();
            if(pos.x == n-1 && pos.y == n-1){   // 도착
                return true;
            }
            for(int i=0; i<4; i++){
                int ny=pos.y+dy[i];
                int nx=pos.x+dx[i];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue;
                if(map[nx][ny] < s || map[nx][ny] > e) continue;
                visited[nx][ny]=true;
                que.add(new Pos(nx, ny));
            }
        }
        return false;
    }

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        map=new int[n][n];
        int max_num=0;
        int min_num=200;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                map[i][j]=sc.nextInt();
                max_num=max(max_num, map[i][j]);
                min_num=min(min_num, map[i][j]);
            }
        }
        int start=0;
        int end=max_num-min_num;
        int mid;        // 차이값
        int answer=200;
        while(start <= end){
            mid=(start+end)/2;
            boolean suc=false;      // 차이값 mid가 성립하는지
            for(int i=min_num; i<=max_num; i++){
                if(i <= map[0][0] && map[0][0] <= i+mid){
                    boolean check=bfs(i, i+mid);
                    visited=new boolean[n][n];      // 초기화
                    if(check){
                        suc=true;
                        break;
                    }
                }
            }
            if(suc){
                answer=min(answer, mid);
                end=mid-1;      // 줄어든다.
            }else{
                start=mid+1;       // 커진다.
            }
        }
        System.out.println(answer);
    }
}

다른 사람의 풀이를 참고해서 완성

if(i <= map[0][0] && map[0][0] <= i+mid)은 탐색을 시작하는 map[0][0]도 범위 안에 있는지 확인하는 것

start는 (최대값-최소값)의 최소값

end는 (최대값-최소값)의 최대값

mid가 (0,0)에서 (n-1, n-1)까지 간 경로에서 최대값-최소값

 

 

# 시간초과
from collections import deque
import sys
import copy
input=sys.stdin.readline

n=int(input())
answer=float('inf')    # 최대-최소가 가장 작아질 때
matrix=list()
for i in range(n) :
    matrix.append(list(map(int, input().split())))

dx=[0, 0, -1, 1]
dy=[-1, 1, 0, 0]
que=deque([[0, 0, {(0, 0)}, 0, 200]])     # x, y, max, min

while que :
    x, y, visit, M, m=que.popleft()     # visit은 튜플 타입인 방문 좌표를 담은 set
    if x == n-1 and y == n-1 :      # 도착
        answer=min(M-m, answer)

    for i in range(4) :
        nx=x+dx[i]
        ny=y+dy[i]
        if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visit:    # 이전 길은 x
            copied=copy.deepcopy(visit)
            copied.add((nx, ny))
            que.append([nx, ny, copied, max(matrix[nx][ny], M), min(matrix[nx][ny], m)])

print(answer)

 

테케를 넣고 실행하니 9.513004064559937초가 나옴 😅

BFS를 썼다.

상하좌우를 탐색했다.

인덱스 범위를 초과하지 않고, 처음 방문한 좌표면 큐에 담았다. 

 

 

👻 다른 사람 풀이

# https://chldkato.tistory.com/67
import sys
from collections import deque
input=sys.stdin.readline
dx=[1, -1, 0, 0]
dy=[0, 0, 1, -1]

def bfs() :
    q=deque()
    c=[[0]*n for _ in range(n)]		# 방문 리스트
    q.append([0, 0])
    c[0][0]=1
    while q :
        x, y=q.popleft()
        if x == n-1 and y == n-1 :		# 도착
            return 1
        for i in range(4) :
            nx=x+dx[i]
            ny=y+dy[i]
            if 0 <= nx < n and 0 <= ny < n :
                if left <= a[nx][ny] <= right and not c[nx][ny] :
                    c[nx][ny]=1
                    q.append([nx, ny])
    return 0

n=int(input())
a, r_max, l_min=[], 0, sys.maxsize
for _ in range(n) :
    row=list(map(int, input().split()))
    a.append(row)
    l_min=min(l_min, min(row))		# 전체 리스트에서 최소값
    r_max=max(r_max, max(row))		# 전체 리스트에서 최대값

# 출발 좌표와 도착 좌표 중 큰 값, 작은 값
l_max=min(a[0][0], a[n-1][n-1])
r_min=max(a[0][0], a[n-1][n-1])

left, right=l_min, r_min
ans=sys.maxsize
while l_min <= left <= l_max and r_min <= right <= r_max :
    l_flag, r_flag=0, 0
    if bfs() :		# 도착했으면 left를 늘려서 범위를 줄이기
        ans=min(ans, right-left)
        left+=1
        l_flag=1
    else :			# 도착못했으면 right를 늘려서 범위를 늘리기
        if l_flag and r_flag :	# 왼쪽과 오른쪽 같이 증가
            left+=1
            right+=1
        else :
            right+=1
            r_flag=1
print(ans)

bfs와 이분 탐색

if l_flag and r_flag는 필요가 없다. true가 될수가 없음