[백준] 14890번: 경사로 (골드3, 파이썬)

https://www.acmicpc.net/problem/14890

14890번: 경사로

아이디어

 

문제를 보고 요구사항을 그대로 구현하였다.

 

우선 길을 가로로 탐색하는 메서드를 작성하였다. 

 

check 메서드

우선 크게 세 가지 경우로 나누었다.

1. 현재 칸이 다음 칸 보다 1만큼 높을 때
2. 현재 칸이 다음 칸 보다 1만큼 낮을 때
3. 현재 칸과 다음 칸이 2 이상 차이가 날 때

위 세가지 경우 중 3번째는 그냥 break 하면 된다.

첫 번째 경우와 두 번째 경우는 각각 낮은 칸을 기준으로 L(경사로의 길이)만큼 검사해주었다.

 

전체 순서는 이렇다.

1. i 값을 증가한다. (N만큼 반복)
2. i번째 라인을 검사하기 위한 line 변수를 초기화해준다. (line = True)
3. j 값을 증가한다. (N만큼 반복)
4. 현재 칸(maps[i][j])이 다음 칸(maps[i][j+1]) 보다 1만큼 높을 때
   1. visited[i][j+1]이 0이면 1로 만들어준다.
   2. visited[i][j+1]이 1이면 line을 False로 변경해주고 break한다. (경사로가 이미 설치되어 있다는 뜻이므로)
   3. 경사로의 길이(L) 만큼 오른쪽 요소들을 검사한다.
      1. 만약 길이가 다른 요소가 있으면 line을 False로 변경해주고 break한다.
5. 현재 칸(maps[i][j])이 다음 칸(maps[i][j+1]) 보다 1만큼 낮을 때
   1. visited[i][j]이 0이면 1로 만들어준다.
   2. visited[i][j]이 1이면 line을 False로 변경해주고 break한다. (경사로가 이미 설치되어 있다는 뜻이므로)
   3. 경사로의 길이(L) 만큼 오른쪽 요소들을 검사한다.
      1. 만약 길이가 다른 요소가 있으면 line을 False로 변경해주고 break한다.
6. 현재 칸(maps[i][j])과 다음 칸(maps[i][j+1])이 2 이상 차이가 날 때
   1. line을 False로 변경해주고 break한다.
7. 3~6번을 N-1만큼 반복 한 후 line이 True 라면 count를 1 증가시킨다.
8. 1~7을 반복한다.

단순 구현이지만 이 순서도를 떠올리고 구현하는데 1시간이나 걸렸다...

 

가로 세로 검사

가로만 검사하는 메서드를 만들었으니 세로도 검사해야 한다.

필자는 maps를 왼쪽으로 90도 돌린 후 메서드를 재사용하기로 했다. 

rmaps = [[0 for _ in range(N)] for _ in range(N)] 
for i in range(N):  # 왼쪽으로 90도 회전
    for j in range(N):
        rmaps[i][j] = maps[j][N-(i+1)]

 

전체 코드

count = 0

def check(maps): 
    global count 

    for i in range(N):

        line = True
        for j in range(N-1):

            if line == False:
                break

            if maps[i][j] - maps[i][j+1] == 1:    # 현재 칸이 다음 칸 보다 1 높으면
                
                if visited[i][j+1] == 0: visited[i][j+1] = 1
                else: 
                    line = False
                    break

                tmp_j = j+1
                for k in range(L - 1):
                    tmp_j += 1
                    if 0 <= tmp_j < N and maps[i][j+1] == maps[i][tmp_j] and visited[i][tmp_j] == 0:
                        visited[i][tmp_j] = 1
                        continue
                    line = False
                    break

            elif maps[i][j] - maps[i][j+1] == -1:    # 현재 칸이 다음 칸 보다 1 낮으면

                if visited[i][j] == 0: visited[i][j] = 1
                else: 
                    line = False
                    break

                tmp_j = j
                visited[i][j] = 1
                for k in range(L - 1):
                    tmp_j -= 1
                    if 0 <= tmp_j < N and maps[i][j] == maps[i][tmp_j]and visited[i][tmp_j] == 0:
                        visited[i][tmp_j] = 1
                        continue
                    line = False
                    break

            elif abs(maps[i][j] - maps[i][j+1]) >= 2: line = False   # 현재 칸과 다음 칸이 2이상 차이나면

        if line == True:
            count += 1


N, L = map(int, input().split())

visited = [[0 for _ in range(N)] for _ in range(N)]
maps = [[int(x) for x in input().split()] for _ in range(N)]
check(maps)


visited = [[0 for _ in range(N)] for _ in range(N)]
rmaps = [[0 for _ in range(N)] for _ in range(N)] 
for i in range(N):  # 왼쪽으로 90도 회전
    for j in range(N):
        rmaps[i][j] = maps[j][N-(i+1)]
check(rmaps)


print(count)