Python3
문제
https://www.acmicpc.net/problem/14890
키워드
- 구현
문제 풀이
문제 요구사항
크기가 N×N인 지도가 있고, 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.
지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다.
길은 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.
길은 총 2N개가 있다.
길을 지나갈 수 있으려면 (1) 길에 속한 모든 칸의 높이가 모두 같아야 한다. 혹은 (2) 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다.
경사로는 높이가 항상 1이며, 길이는 L이다. (개수는 매우 많아 부족할 일이 없다.)
- 경사로의 조건
- 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
- 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다. (abs 함수 사용)
- 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.
지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램
변수 및 함수 설명
n, l: 지도의 크기 N (2 ≤ N ≤ 100), 경사로 크기 L (1 ≤ L ≤ N)
runway: 지도 정보 (각 칸의 높이는 10보다 작거나 같은 자연수이다.)
cnt: 지나갈 수 있는 길의 개수
used: 경사로를 놓을 수 있는 리스트
way(): 길이 몇 개 가능한지 탐색하는 함수
풀이
(입력 및 선언)
- 지도의 크기 n, 경사로의 크기 l을 입력받는다
- 지도 정보를 입력받고 저장한다
- 가능한 길의 개수를 나타내는 cnt 변수를 선언하고 초기화한다.
(지도의 가로 방향 길)
- 경사로가 가능한지 확인하는 리스트를 선언한다.
- 가로 한 줄 씩(runway[i]) way()에 넣을 건데, 만약 way() 함수에서 True가 반환되면 cnt 값을 1 증가시킨다.
(지도의 세로 방향 길)
- 경사로가 가능한지 확인하는 리스트를 선언한다.
- 세로 한 줄 씩 way()에 넣을 건데, 만약 way() 함수에서 True가 반환되면 cnt 값을 1 증가시킨다.
- 이때, 세로 방향은 [runway[j][i] for j in range(n)]로 나타낼 수 있다.
(way 함수)
- 매개변수는 가로 한 줄, 혹은 세로 한 줄이다.
- 1부터 n까지 반복한다.
- 만약 이전 위치의 높이와 현재 위치의 높이 차가 1 이상이라면, 경사로를 놓을 수 없기 때문에 False를 반환한다.
- 현재 < 이전 높이일 때는, 오른쪽을 기준으로 살펴 보고 경사로를 놓을 것이다. (경사로는 낮은 칸에 위치한다고 제시)
- 경사로의 크기만큼 반복한다. (경사로 크기 l만큼 필요)
- 만약 지도의 범위를 넘어가 거나, 이미 설치한 곳이거나, 높이가 다르면 False를 반환한다.
- 만약 높이가 같으면 경사로 설치 (used[i+j] = True)
- 현재 > 이전 높이일 때는, 왼쪽을 기준으로 살펴보고 경사로를 놓는다.
- 경사로의 크기만큼 반복한다.
- 만약 범위를 넘어가 거나, 이미 설치한 곳이거나, 높이가 다르면 False.
- 두 높이가 같으면 경사로 설치 (used[i-j-1] = True)
- 그 외 경우(모두 높이가 똑같을 때) True 반환
(최종 출력)
- cnt 값 출력하기
최종 코드
n, l = map(int, input().split())
runway = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
def way(pos):
for i in range(1, n):
if abs(pos[i] - pos[i-1]) > 1:
return False
if pos[i] < pos[i-1]:
for j in range(l):
if i + j >= n or used[i+j] or pos[i] != pos[i+j]:
return False
if pos[i] == pos[i+j]:
used[i+j] = True
elif pos[i] > pos[i-1]:
for j in range(l):
if i - j - 1 < 0 or used[i-j-1] or pos[i-1] != pos[i-j-1]:
return False
if pos[i-1] == pos[i-j-1]:
used[i-j-1] = True
return True
# 가로
for i in range(n):
used = [False for _ in range(n)]
if way(runway[i]):
cnt += 1
# 세로
for i in range(n):
used = [False for _ in range(n)]
if way([runway[j][i] for j in range(n)]):
cnt += 1
print(cnt)피드백
역시 삼* 문제 어렵다.. 그래프 같이 보이면서도 그냥 쌩구현인..
I mean