[SWEA] 4014 활주로 건설 (Python) - Simulation

📌 문제

1. 격자의 각 셀에는 지형의 높이가 정수로 주어져 있다.

 

2. 목표는 가로 또는 세로 방향으로 활주로를 건설할 수 있는 경우의 수를 구하는 것이다.

 

3. 같은 줄에 높이가 다른 구간이 있다면 반드시 아래와 같은 경사로를 설치해줘야 한다.

• 경사로의 길이: X ( 2 <= X <= 4)
• 경사로의 높이: 1

4. 아래는 문제에서 주어진 모든 경우를 나타낸 것이다.

 

4. 문제에서 주어진 경사로 건설 규칙에 따라 경사로를 건설하면, 예제에 대한 정답은 다음과 같이 7이 된다.

---

📌 풀이

Code

T = int(input())
for tc in range(1, 1+T):
    N, X = map(int, input().split())    # N: 맵 크기, X: 활주로 길이
    arr = [list(map(int, input().split())) for _ in range(N)]   # 맵
    CNT = 0     # 활주로를 건설할 수 있는 경우의 수 (정답 변수)
    
    
    # 세로로 읽기
    for c in range(N):
        prev = arr[0][c]        # 이전 위치의 높이
        conti = 1               # 동일 높이 연속으로 나온 횟수
        visited = [0] * N       # 방문 리스트 (이미 건설된 곳에 또 건설하는 것 막기 위함)
        for r in range(1, N):
            # 이미 건설된 곳이면 넘어가
            if visited[r]:
                continue
            
            cur = arr[r][c]     # 현재 위치의 높이
            conti += 1
            
            # 순서대로 읽다가 높이가 한번에 2 이상 차이나면 그 줄은 제외
            if abs(cur - prev) >= 2:
                break
            
            # 한 칸 내려갔으면 지금부터 동일 높이 연속 X개 여부 확인
            if cur - prev == -1:
                break_flag = False
                for k in range(X):
                    nr = r + k
                    # 배열을 벗어나지 않으면서 동일 높이가 연속으로 나오면
                    if nr < N and cur == arr[nr][c]:
                        visited[nr] = 1     # 방문 처리
                    # 배열 벗어나거나 높이가 바뀌면 break
                    else:
                        break_flag = True
                if break_flag:
                    break
                conti = 0       # 동일 높이 연속 횟수 초기화
            
            # 한 칸 올라갔으면 지금까지 동일 높이 연속 X개 여부 확인
            elif cur - prev == 1:
                conti -= 1
                if conti < X:
                    break
                conti = 1       # 동일 높이 연속 횟수 초기화
            
            prev = cur
        
        # for-else문: 한 번도 break에 걸리지 않았다면
        else:
            CNT += 1

    
    # 가로로 읽기
    for r in range(N):
        prev = arr[r][0]        # 이전 위치의 높이
        conti = 1               # 동일 높이 연속으로 나온 횟수
        visited = [0] * N       # 방문 리스트 (이미 건설된 곳에 또 건설하는 것 막기 위함)
        for c in range(1, N):
            # 이미 건설된 곳이면 넘어가
            if visited[c]:
                continue
            
            cur = arr[r][c]     # 현재 위치의 높이
            conti += 1
            
            # 순서대로 읽다가 높이가 한번에 2 이상 차이나면 그 줄은 제외
            if abs(cur - prev) >= 2:
                break
            
            # 한 칸 내려갔으면 지금부터 동일 높이 연속 X개 여부 확인
            if cur - prev == -1:
                break_flag = False
                for k in range(X):
                    nc = c + k
                    # 배열을 벗어나지 않으면서 동일 높이가 연속으로 나오면
                    if nc < N and cur == arr[r][nc]:
                        visited[nc] = 1     # 방문 처리
                    # 배열 벗어나거나 높이가 바뀌면 break
                    else:
                        break_flag = True
                if break_flag:
                    break
                conti = 0       # 동일 높이 연속 횟수 초기화
            
            # 한 칸 올라갔으면 지금까지 동일 높이 연속 X개 여부 확인
            elif cur - prev == 1:
                conti -= 1
                if conti < X:
                    break
                conti = 1       # 동일 높이 연속 횟수 초기화
            
            prev = cur
        
        # for-else문: 한 번도 break에 걸리지 않았다면
        else:
            CNT += 1
     
            
    print(f'#{tc} {CNT}')

---

Solution

1. 각 열과 각 행을 따로 읽으며 활주로 가능 여부를 확인

 

2. 앞으로 가다가 높이가 2 이상 차이나면 종료

 

3. 현재 높이와 1 차이가 나는 지형으로 이동했을 시 경사로 설치 여부 확인  

• 낮은 지형으로 내려갔을 때
  • conti를 0으로 바꾸고 X개의 칸 만큼 방문 처리 (X개만큼 못가면 그 줄은 탈락)
  • 방문처리 된 칸은 이동하더라도 conti가 늘어나지 않음
• 높은 지형으로 올라갔을 때
  • 지금까지의 conti(동일한 높이인 칸이 연속으로 나온 횟수)가 X보다 작으면 그 줄은 탈락
  • 비교 후에 conti는 1로 변경 (새로운 칸에 올라온 상태이므로) 

4. 각 줄을 확인하면서 break 조건에 단 한번도 걸리지 않은 경우에만 CNT 1 증가시키기

• for-else 문 활용

5. 모든 줄을 다 확인한 후, CNT 출력

---

깨달은 점

그냥 빡구현 문제라.. 삽질하며 깨달은 건 반례를 잘 찾아야 한다는 것..

 

그리고 가장 중요한 것은..

키보드에 손을 올리기 전에 완벽하게 설계하고 시작하는 습관을 들이자.