[Python 파이썬] SWEA 11315번 - 오목 판정

2024년 5월 14일

문제 링크 : SWEA 11315번 - 오목 판정

SW Expert Academy

 

---

 

 

문제 접근

 

N x N 사이즈의 판이 주어지고, 돌이 놓아진 곳은 o , 아닌 곳은 . 문자를 표기한다.

 

우리가 아는 오목과 같이 가로, 세로, 대각선 중 하나의 방향으로 다섯 개 이상 연속한 돌이 있는지 판정하면 되는 문제이다.

 

---

 

먼저 가로, 세로, 대각선 방향으로 한 칸씩 전진하며 탐색해야 하기에 다음과 같이 8방향을 탐색하기 위한 두 배열을 선언해주어야 한다.

 

# 동, 남동, 남, 남서, 서, 북서, 북, 북동
d_row = [0, 1, 1, 1, 0, -1, -1, -1]
d_col = [1, 1, 0, -1, -1, -1, 0, 1]

 

현재 인덱스가 [1, 1] 이고, 남서 방향으로 한 칸씩 전진하여 탐색하려 한다면

 

[1 + d_row[3], 1 + d_col[3]] = [1 + 1, 1 - 1] = [2, 0]으로 나타낼 수 있다.

 

다음과 같이 5 X 5 사이즈의 보드가 주어지고, 파란색 원 위치에 돌을 놓았다고 가정해보자

 

 

 

[0, 1] 위치의 돌을 기준으로 8방향을 확인해보며 연속된 5가지 돌이 있는지 탐색하면 된다.

 

 

동쪽으로 한 칸 더 전진해보니 돌이 없으니 다음 방향으로 넘어간다.

 

 

남동쪽 방향으로 계속 돌이 있어, 전진해보다 5개가 되기 전에 돌이 끊켰기에 다음 방향으로 넘어간다.

 

 

남쪽 방향으로 돌이 있어, 계속 전진해보니 5개의 돌이 연속되어있음을 탐색을 통해 알아냈으므로 YES를 출력하고 이후 추가 탐색은 생략한다.

 

---

 

순서도

 

1. 8방향 탐색을 제어하기 위한 d_row, d_col 배열을 선언한다.

2. N * N 크기의 board를 입력받는다.

3. 모든 행을 순회하며 만약 돌이 존재한다면 8방향 모두 한 칸씩 전진해보며 5개 연속한 케이스가 존재하는지 완전 탐색을 진행한다.

4. 존재한다면 YES, 아니라면 NO를 출력하고 로직을 종료한다.

 

---

 

입력 예제

 

1
5
....o
...o.
..o..
.o...
o....

 

---

 

출력 예제

 

#1 YES

 

---

 

 

주의할 점

 

암시적 그래프 탐색의 성격을 띄므로 탐색을 위한 d_row, d_col 배열 선언과 활용이 중요하다.

---

 

전체 코드

 

def isValid(row, col):
    if 0 <= row < N and 0 <= col < N and board[row][col] == "o":
        return True
    return False

def solution():
    for row in range(N):
        for col in range(N):
            if board[row][col] == "o":
                for i in range(8):
                    matched = 1
                    next_row = row
                    next_col = col

                    while matched <= 5:
                        next_row += d_row[i]
                        next_col += d_col[i]
                        if isValid(next_row, next_col):
                            matched += 1
                        else:
                            break
                
                    if matched == 5:
                        return "YES"
    
    return "NO"
                    

T = int(input())

# 동, 남동, 남, 남서, 서, 북서, 북, 북동
d_row = [0, 1, 1, 1, 0, -1, -1, -1]
d_col = [1, 1, 0, -1, -1, -1, 0, 1]

for test_case in range(1, T + 1):
    N = int(input())

    board = []

    for _ in range(N):
        board.append(input())

    print(f'#{test_case} {solution()}')