[Python] [백준] 8976번: LAGNO

www.acmicpc.net/problem/8976

8976번: LAGNO

 

문제

Lagno (also known as Reversi and Othello) is a board game for two players, one black and one white. The board is square, consisting of 8 rows and 8 columns. 

In one move, the black player places a black piece into an empty square so that, in at least one of eight directions (up, down, left, right and the four diagonal directions), there is a row of white pieces between the newly placed piece and some other black piece. After placing, all white pieces between (in any direction) the newly placed black piece and pre-existing black pieces become black. 

Write a program that, for a given board layout, calculates the largest number of white pieces the black player can convert in one move.

입력

The input contains eight lines, each consisting of exactly eight characters '.', 'B' or 'W'. The character '.' represents an empty square, the letter 'B' a square with a black piece, and the letter 'W' a square with a white piece. 

출력

Output the largest number of white pieces that black can convert in a single move. If there are no legal moves, output 0. 

 

풀이

8X8 배열을 입력 받은 다음 nx와 ny의 범위가 0이상 8미만인지 체크하며 배열을 순회하였다.

하지만 계속 런타임에러(IndexError)가 발생하게 되었고..

nx와 ny가 배열의 잘못된 인덱스를 접근하지 않도록 범위 체크를 모든 곳에서 해주었으나 결국 성공하지 못했다..

 

다음은 런타임에러가 발생하는 파이썬(Python) 코드이다.

import sys
input = sys.stdin.readline

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

board = [list(input().strip()) for _ in range(8)]
answer = 0

for x in range(8):
    for y in range(8):
        if board[x][y] != '.':
            continue

        total_count = 0

        # 8가지 방향 탐색
        for i in range(8):
            partial_count = 0
            nx = x + dx[i]
            ny = y + dy[i]

            # 8X8 범위 안에 있는지 검사
            if 0 <= nx < 8 and 0 <= ny < 8:
                # 흰 돌이 연이어 있으면 계속 같은 방향으로 탐색
                while board[nx][ny] == 'W':
                    nx += dx[i]
                    ny += dy[i]
                    partial_count += 1

                    if 0 <= nx < 8 and 0 <= ny < 8:
                        break

                # 연속된 흰 돌 이후에 검은 돌이 오는 경우 총 개수에 합산
                if 0 <= nx < 8 and 0 <= ny < 8:
                    if board[nx][ny] == 'B':
                        total_count += partial_count

        answer = max(answer, total_count)

print(answer)

 

해결책으로 8X8 배열의 상하좌우를 'x' ('B'나 'W'가 아닌 아무거나)로 둘러싸서 10X10 배열로 변환한다.

이동을 하다가 'x'에 도착하게 되면 while문도 탈출하고, total_count의 값에 partial_count 값을 더해주는 if문이 실행되지 않는다.

따라서 자연스럽게 nx와 ny에 대한 범위 체크가 필요하지 않은 것이다.

 

다음은 맞았습니다를 받은 파이썬(Python) 코드이다.

import sys
input = sys.stdin.readline

dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]

# 8X8 영역에 x를 둘러 10X10 배열로 변환
board = [['x'] * 10] + [['x'] + list(input().strip()) + ['x'] for _ in range(8)] + [['x'] * 10]
answer = 0

for x in range(1, 9):
    for y in range(1, 9):
        if board[x][y] != '.':
            continue

        total_count = 0

        # 8가지 방향 탐색
        for i in range(8):
            partial_count = 0
            nx = x + dx[i]
            ny = y + dy[i]

            # 흰 돌이 연이어 있으면 계속 같은 방향으로 탐색
            while board[nx][ny] == 'W':
                nx += dx[i]
                ny += dy[i]
                partial_count += 1

            # 연속된 흰 돌 이후에 검은 돌이 오는 경우 총 개수에 합산
            if board[nx][ny] == 'B':
                total_count += partial_count

        answer = max(answer, total_count)

print(answer)