[BOJ/Python] 22116_창영이와 퇴근

문제 출처:https://www.acmicpc.net/problem/22116

22116번: 창영이와 퇴근

문제

창영이의 퇴근길은 출근길과 조금 다르다. 창영이는 건강을 위해 따릉이를 빌려 타고 퇴근하는 습관을 기르고 있다.

창영이의 퇴근길은 N×N 크기의 격자로 표현된다. 창영이는 A1,1에서 출발하여 AN,N까지 이동할 계획이다. 창영이는 상하좌우 인접한 격자로 한 번에 한 칸씩 이동할 수 있다. 각 격자 Ar,c에는 자연수가 적혀 있는데, 이는 해당 지역의 높이를 뜻한다. 인접한 격자 사이의 높이 차이의 절댓값을 경사라고 하고, 경사가 클수록 경사가 가파르다고 하자.

따릉이는 가격에 따라 성능이 다르다. 비싼 따릉이는 경사가 가파르더라도 내리지 않고 타고 갈 수 있지만, 값싼 따릉이는 경사가 가파르면 힘들고 위험하기 때문에 내려서 이동해야 한다.

창영이는 최소한의 비용으로 따릉이를 빌려서, 따릉이에서 한 번도 내리지 않고 집에 도착하고 싶다. 그러기 위해선 창영이가 지날 수 있는 최대 경사의 최솟값을 알아야만 한다. 여러분들이 창영이를 도와주자.

입력

첫째 줄에 격자의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 격자의 높이 정보가 주어진다. 첫 번째로 주어지는 값이 A1,1이고, 마지막으로 주어지는 값이 AN,N이다.

출력

A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다.

제한

• 1 ≤ N ≤ 1,000
• 1 ≤ Ar,c ≤ 1,000,000,000

예제 입력 1

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

예제 출력 1

0

예제 입력 2

3
3 4 3
2 5 2
5 2 2

예제 출력 2

1

---

풀이

 

문제를 요약해보자.

1. 인접한 칸 사이의 차가 경사이다.
2. 1,1 에서 n,n으로 이동할 때, 만나는 경사의 최대가 최솟값이 될 수 있도록 하여야 한다.
3. 이때 그 경사의 값을 출력하는 문제이다.

 

풀이는 다음과 같다.

1. 단순하게 모든 경로의 정보를 간선 리스트에 저장하고, 오름차순으로 정렬하였다.
2. 간선들을 가중치(이 문제에서의 경사)가 작은 것들부터 하나씩 살펴보며 연결한다.
3. 만약 연결하였을 때, 1,1과 n,n이 연결되었다면 이동하는 경로를 찾은 것이므로 해당 경사가 현재 경로에서의 최대 경사가 된다.
4. 경사를 출력한다.

코드는 다음과 같다.

 

import sys
 
def find_parent(parent,x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
 
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
 
 
n = int(sys.stdin.readline())
parent = [i for i in range(n*n)]
 
grid = []
for _ in range(n):
    grid.append(list(map(int,sys.stdin.readline().split())))
 
edges = []
 
for i in range(n-1):
    for j in range(n-1):
        edges.append(((abs(grid[i][j]-grid[i][j+1])),i*n+j,i*n+j+1))
        edges.append(((abs(grid[i][j]-grid[i+1][j])),i*n+j,(i+1)*n+j))
 
for i in range(n-1):
    edges.append(((abs(grid[i][n-1]-grid[i+1][n-1])),i*n+n-1,(i+1)*n+n-1))
 
for j in range(n-1):
    edges.append(((abs(grid[n-1][j]-grid[n-1][j+1])),(n-1)*n+j,(n-1)*n+j+1))
 
edges.sort()
 
for w,a,b in edges:
    union_parent(parent,a,b)
    if find_parent(parent,0)==find_parent(parent,n*n-1):
        print(w)
        break
 
if n==1:
    print(0)