[Python, 파이썬] SWEA 11315. 오목 판정

 

N X N 크기의 판이 있다. 돌이 가로, 세로, 대각선 중 하나의 방향으로
다섯 개 이상 연속한 부분이 있는지 없는지 판정하는 문제.

 

 

 

def continuous(word): # 연속된 오목 5개가 있는지 확인하는 함수

    # 세로, 가로, 대각선, 역대각선
    dx = [1, 0, 1, 1]
    dy= [0, 1, 1, -1]
    
    for i in range(N):
        for j in range(N):
            if(word[i][j]=='o'): # 돌이 있으면

                for k in range(4): # 상하좌우 체크

                    x = i
                    y = j
                    cnt = 0 # 카운트

                    while(x < N) and (0<= y < N) and (word[x][y]=='o'):
                        
                        x += dx[k] # 한쪽 방향으로 계속 간다
                        y += dy[k] 
                        cnt += 1

                        if(cnt == 5):
                            return 'YES'

    return 'NO'


T = int(input()) # 테스트케이스 수 개

for test_case in range(1, T+1):

    N = int(input()) # 보드판의 크기 N*N
    board = [] # 게임을 하는 판

    # 오목판 입력받기
    for i in range(N):
        board.append(input())

    # 오목판 체크
    answer = continuous(board)

    print("#%d %s" %(test_case, answer))

 

 

 

[문제풀이]

---

 

처음에 이 문제, 원본 행렬과 전치 행렬.

대각선과 역대각선을 구해서 돌이 5개 이상인지 체크하기만 하면 되는줄 알았다.

그런데 테스트케이스 중 93% 정답률에서 벗어나지 않아서 체크해보니, 치명적인 실수가 있던걸 깨달았다.

 

 

일반적인 0, 0에서 N, N까지 대각선중 돌이 연속적으로 5개 이상인지 확인해야 하는 거 뿐만 아니라, 이렇게 모든 대각선을 확인해야 한다.

 

그래서 고민하던 중 다른 분의 코드를 참고해서 풀게 됬다.

# 세로, 가로, 대각선, 역대각선
dx = [1, 0, 1, 1]
dy= [0, 1, 1, -1]

 

현재 위치 (i, j)에서 아래, 옆, 대각선, 역대각선 각각 체크해 돌의 개수가 연속적으로 나오는지 확인해야 한다.

이렇게 현재 위치의 상하좌우를 확인하기 위해 i, j에 세로는 (1, 0), 가로는 (0, 1), 대각선은 (1, 1), 역대각선은 (1, -1)을 더해준다.

while(x < N) and (0<= y < N) and (word[x][y]=='o'):
    x += dx[k] # 한쪽 방향으로 계속 간다
    y += dy[k] 
    cnt += 1

 

정해진 NxN을 벗어나지 않고, 그리고 돌이 놓여있으면 계속 그 방향대로 가면서 돌의 개수를 더해준다.

그리고 돌의 개수가 5개가 되면 YES.

모든 반복문을 돌았는데도 발견하지 못하면 NO다.