[백준/Python] 17300번: 패턴

문제

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

17300번: 패턴

---

문제 요약

패턴을 나타내는 수열 A가 주어졌을 때, 유효한 패턴이라면 "YES", 그렇지 않다면 "NO"를 출력한다.

 

패턴에는 다음과 같은 제약이 있다.

 

1. 패턴의 길이는 3 이상이다.

2. 패턴을 나타내는 수열에는 같은 점이 두 번이상 등장하지 않는다.

3. 수열의 인접한 점을 연결해 만든 선분 위에는 아직 등장하지 않은 점이 있을 수 없다.

---

코드

from collections import deque

# 3 * 3 배열에 해당하는 인덱스 반환
def idx(num):
    num -= 1
    return [(num // 3), (num % 3)]

l = int(input())

# 큐를 이용해 왼쪽에서 원소 추출
arr = deque(map(int, input().split()))

# 패턴에서 지나간 점을 체크하는 배열
board = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 

# 길이가 3 이상이거나, 중복된 점이 있다면 유효한 패턴 X
if len(arr) < 3 or len(arr) != len(set(arr)):
    print("NO")
    exit()
    
# 시작 점 인덱스 구하기
start_num = arr.popleft()
cur_idx = idx(start_num)
board[cur_idx[0]][cur_idx[1]] = 1

# 패턴 수열에서 하나씩 순서대로 추출하여 검사
while arr:
    # 다음 점의 인덱스 구하기
    next_num = arr.popleft()
    next_idx = idx(next_num)
    board[next_idx[0]][next_idx[1]] = 1
    
    # 3가지 상황에 따라 다르게 지나갈 수 있는 점 파악

    # 현재 점과 다음 점이 같은 행에 있는 경우
    if cur_idx[0] == next_idx[0]:
        between_idx = [cur_idx[0], abs(next_idx[1] - cur_idx[1]) / 2]
        if between_idx[1] == 1.0 or between_idx[1] == 0.0:
            if board[int(between_idx[0])][int(between_idx[1])] == 0:
                print("NO")
                exit()   
                
    # 현재 점과 다음 점이 같은 열에 있는 경우
    elif cur_idx[1] == next_idx[1]:
        between_idx = [abs(next_idx[0] - cur_idx[0]) / 2, cur_idx[1]]
        if between_idx[0] == 1.0 or between_idx[0] == 0.0:
            if board[int(between_idx[0])][int(between_idx[1])] == 0:
                print("NO")
                exit()
    
    # 현재 점과 다음 점이 대각선상에 있는 경우
    else:
        between_idx = [abs(next_idx[0] - cur_idx[0]) / 2, abs(next_idx[1] - cur_idx[1]) / 2]
        if (between_idx[1] == 1.0 or between_idx[1] == 0.0) and (between_idx[0] == 1.0 or between_idx[0] == 0.0):
            if board[int(between_idx[0])][int(between_idx[1])] == 0:
                print("NO")
                exit()
                
    #print(between_idx)
    
    cur_idx = next_idx
            
print("YES")

---

코드 설명

1. 1 ~ 9의 숫자가 3 * 3 배열 (패턴)에 해당하는 인덱스를 반환하는 함수 idx를 생성한다.

 

2. 큐를 이용하여 왼쪽에서 하나씩 다음 패턴을 추출하여 조건에 맞는지 검사한다.

 

3. 현재 점과 다음 점 사이에 있는 점이 등장한 적이 있는지 경우를 나누어 검사한다.

 

3 - 1. 현재 점과 다음 점이 같은 행에 있는 경우ex) 현재 점: 6, 다음 점: 4, 가운데 점: 5

1	2	3
4	5	6
7	8	9

 

3 - 2. 현재 점과 다음 점이 같은 열에 있는 경우

ex) 현재 점: 8, 다음 점: 2, 가운데 점: 5

1	2	3
4	5	6
7	8	9

 

3 - 3. 현재 점과 다음 점이 대각선 상에 있는 경우

ex) 현재 점: 9, 다음 점: 1, 가운데 점: 5

1	2	3
4	5	6
7	8	9