https://www.acmicpc.net/problem/14890
문제 크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.
오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.
다음과 같은 N=6인 경우 지도를 살펴보자.
이때, 길은 총 2N개가 있으며, 아래와 같다.
길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.
아래와 같은 경우에는 경사로를 놓을 수 없다.
경사로를 놓은 곳에 또 경사로를 놓는 경우
낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
경사로를 놓다가 범위를 벗어나는 경우
결국 이번 문제는 조건을 얼마나 충실하게 구현할 수 있는가 문제이다.
여기서 4가지 조건을 고려해볼 수 있다.
모든 칸의 블럭 갯수가 같을때 (할거없음)
뒤의 블럭이 앞의 블럭보다 1개 높을때
앞의 블럭이 뒤의 블럭보다 1개 높을때
블럭이 두칸이상 높을때 (할 수 없음)
결국 2번과 3번의 조건을 잘 이행하면 된다는 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n, l = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
result = 0
# 1. 가로 확인
for i in range(n):
used = [False for _ in range(n)]
if pos(graph[i]):
result += 1
# 2. 세로 확인
for i in range(n):
used = [False for _ in range(n)]
if pos([graph[j][i] for j in range(n)]):
result += 1
필요한 값과 가로와 세로를 각각 확인하는 for문입니다. 그리고 그 해당하는 줄은 이동이 가능한지 판단한 pos함수를 보겠습니다. 그리고 경사로를 체크하기 위한 used라는 리스트를 하나 생성합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def pos(now):
for j in range(1, n):
# 1. 차이가 1만 가능
if abs(now[j] - now[j - 1]) > 1:
return False
# 2. 현재 < 이전, 경사로를 만들기 위해 오른쪽을 스캔함(낮은 곳에 경사로 설치)
if now[j] < now[j - 1]:
# l 만큼 경사로 너비 필요
for k in range(l):
# 범위 넘어감 or 이미 설치함 or 낮은 곳의 높이가 다른 경우, 그만
if j + k >= n or used[j + k] or now[j] != now[j + k]:
return False
# 높이가 같은 경우 사용 여부 체크
if now[j] == now[j + k]:
used[j + k] = True
# 3. 현재 > 이전, 경사로를 만들기 위해 왼쪽을 스캔함
elif now[j] > now[j - 1]:
for k in range(l):
# 범위 넘어감 or 이미 설치함 or 낮은 곳의 높이가 다른 경우, 그만
if j - k - 1 < 0 or now[j - 1] != now[j - k - 1] or used[j - k - 1]:
return False
# 높이가 같은 경우 사용 여부 체크
if now[j - 1] == now[j - k - 1]:
used[j - k - 1] = True
# 모두 문제없이 설치된 경우 가능함을 출력
return True
for문은 일단 길의 처음부터 끝까지 순회를 합니다. 조건에서 지도는 nxn 정사각형이니 1부터 n까지 봅시다.
일단 조건 4번 고저차이가 1보다 클때의 경우 바로 False를 반환을 합시다.
이어서 두번째 for문을 봅시다. 만약 차이가 난다면(앞의 조건에서 길이 차이가 1이하라면) for문을 한번더 돌게 되는데 이때 l은 처음에 받은 경사로의 길이 입니다.
이제 조건을 보면 첫번째는 j+k가 전체 길이를 넘었을때, 또는 이미 경사로가 설치되었는지 마지막으로 낮은 곳의 높이가 다른 경우(3 - 2 - 1) 경사로를 설치할 수 없으니 False를 반환합니다. 마지막으로 경사로 길이 l만큼 높이가 같을 경우에만 True를 반환합니다.
만약 순방향, 역방향 모두 경사로가 설치할 수 있다면 순방향먼저 체크한다고 보시면 됩니다.
이어서 elif는 반대방향으로 경사로를 설치하기 위해서 살펴봅시다.
똑같이 범위를 초과하는가 이미 설치되었던가 낮은 곳이 높이가 다른 경우 False를 반환
경사로가 설치되지 않으며 낮은 곳의 높이가 같은 경우 사용 여부를 체크를 합니다.
이 모든 조건을 문제가 없이 설치된 경우 가능하다고 출력을 합니다.
Comments powered by Disqus.