[백준] 오목 (2615번)

난이도 : Silver 1
Link : https://www.acmicpc.net/problem/2615
Tag : 구현, 브루트포스 알고리즘
풀이일자 : 2024년 9월 19일

📌 문제 탐색하기

본 문제는 오목에 대한 기초적인 문제이다.
어떤 플레이어가 이겼는지 확인하는 문제이다.

1, 2는 플레이어의 색을 의미한다.

가능한 시간복잡도

오목판의 크기는 19 x 19 이므로 모든 오목판을 탐색하면서 1또는 2가 있을때 연속해서 몇개의 돌이 있는지 계산하면 되므로 시간 복잡도상의 문제는 없을 것으로 보인다.

📌 문제 접근 방법

오목판을 탐색하여 1 또는 2가 존재했을 때 오목이 될 수 있는 방향대로 5개의 오목알이 존재하는지 확인할 것이다.

또한 출력 조건에서 다섯개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로 일경우 가장 위) 라는 조건을 충족 시키기 위해서 탐색하는 과정에서 8방향으로 탐색하는것이 아니라 4방향으로 탐색하여 중복 탐색되는 것을 막고 출력할 조건을 만족할 예정이다.

📌 코드 설계하기

1. grid를 입력받는다. (바둑판 상황)

2. omok 플래그를 False로 설정한다.

3. 중복을 제외하고 출력 형식을 맞출 탐색 방향 4가지를 추가한다.

   dx = [1, 1, 1, 0] # 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래
   dy = [0, 1, -1, 1] # 방향에 따른 y 변화

4. grid를 탐색하여 1또는 2인것을 찾는다.

5. 찾았다면 4방향으로 탐색하여 갯수를 센다.

        if grid[i][j] != 0:  # 바둑알이 있는 경우
            player = grid[i][j]
            for m in range(4):  # 4방향 탐색 (반대방향은 하지 않음)
                cnt = 1  # 현재 위치에서 시작
                nx, ny = j, i  # 현재 위치

                # 5개의 돌이 연속적으로 있는지 확인
                for k in range(4):  # 최대 4칸 더 탐색 (총 5칸)
                    nx += dx[m]
                    ny += dy[m]
                    if 0 <= nx < 19 and 0 <= ny < 19 and grid[ny][nx] == player:
                        cnt += 1
                    else:
                        break

6. 돌의 개수가 5개라면 6목인지 아닌지 판단한다.

# 5개의 돌이 연속되는 경우
                if cnt == 5:
                    # 6목인지 확인 (앞쪽 돌이 같은지)
                    prev_x = j - dx[m]
                    prev_y = i - dy[m]
                    if not (0 <= prev_x < 19 and 0 <= prev_y < 19 and grid[prev_y][prev_x] == player):
                        # 6목인지 확인 (뒤쪽 돌이 같은지)
                        next_x = nx + dx[m]
                        next_y = ny + dy[m]
                        if not (0 <= next_x < 19 and 0 <= next_y < 19 and grid[next_y][next_x] == player):
                            print(player)  # 승리한 돌 색 출력
                            print(i + 1, j + 1)  # 시작 좌표 출력 (가장 왼쪽/위쪽 돌 좌표)
                            omok = True
                            break

7. omok플래그가 false라면 0을 출력한다.

📌 시도 회차 수정 사항

1. 틀렸습니다. (8%)
   시작좌표를 출력하는데 문제점이 있었다. 가로 방향과 세로방향을 신경쓰지 못해 출력하는 방향을 재 지정하였다.
2. 틀렸습니다. (18%)
   시작좌표를 출력하는데 문제점이 있었다. 대각선일 경우 위에 있는 것을 출력해야하는데 중복된 탐색 때문에 아랫부분을 출력하는 경우도 존재하였다.
3. 틀렸습니다. (25%)
   아직 승부가 결정되지 않았을 경우 0을 출력해야하는데 이에 대한 조건을 추가하지 않았다.

📌 정답 코드

grid = []

for i in range(19):
    grid.append(list(map(int, input().split())))

dx = [1, 1, 1, 0]  # 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래
dy = [0, 1, -1, 1]  # 방향에 따른 y 변화

omok = False

for i in range(19):  # i는 y좌표
    if omok:
        break
    for j in range(19):  # j는 x좌표
        if omok:
            break
        if grid[i][j] != 0:  # 바둑알이 있는 경우
            player = grid[i][j]
            for m in range(4):  # 4방향 탐색 (반대방향은 하지 않음)
                cnt = 1  # 현재 위치에서 시작
                nx, ny = j, i  # 현재 위치

                # 5개의 돌이 연속적으로 있는지 확인
                for k in range(4):  # 최대 4칸 더 탐색 (총 5칸)
                    nx += dx[m]
                    ny += dy[m]
                    if 0 <= nx < 19 and 0 <= ny < 19 and grid[ny][nx] == player:
                        cnt += 1
                    else:
                        break

                # 5개의 돌이 연속되는 경우
                if cnt == 5:
                    # 6목인지 확인 (앞쪽 돌이 같은지)
                    prev_x = j - dx[m]
                    prev_y = i - dy[m]
                    if not (0 <= prev_x < 19 and 0 <= prev_y < 19 and grid[prev_y][prev_x] == player):
                        # 6목인지 확인 (뒤쪽 돌이 같은지)
                        next_x = nx + dx[m]
                        next_y = ny + dy[m]
                        if not (0 <= next_x < 19 and 0 <= next_y < 19 and grid[next_y][next_x] == player):
                            print(player)  # 승리한 돌 색 출력
                            print(i + 1, j + 1)  # 시작 좌표 출력 (가장 왼쪽/위쪽 돌 좌표)
                            omok = True
                            break
if omok == False:
    print(0)