Being Programmer

[백준][파이썬] 16924번 - 십자가 찾기

문제 번호 : 16924

문제 출처 : https://www.acmicpc.net/problem/16924

Code

import sys

n, m = map(int, input().split())
board = [list(sys.stdin.readline().strip()) for _ in range(n)]
answer =[]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

if board[0][0] == '*' or board[0][m-1] == '*' or board[n-1][0] == '*' or board[n-1][m-1]=='*':
    print(-1)
    # 각 모서리에 * 이 있으면 십자가는 찾을 수 있어도 십자가로 그 별을 커버하지 못한다.
else:
    for i in range(1, n-1):
        for j in range(1, m-1):
            if board[i][j] == '*':
                max_size = min(i, j, n-i-1, m-j-1)
                # 십자가의 최대 크기는 상하좌우의 공백길이의 최소값
                for k in range(1, 1 + max_size):
                    count = 0
                    for idx in range(4):
                        nx = i + k * dx[idx]
                        ny = j + k * dy[idx]
                        if board[nx][ny] != '*':
                            break
                        else: count += 1
                    if count == 4:
                        answer.append((i, j, k))
                    else:
                        break
    # board에서 찾은 십자가 위치를 모두 . 으로 바꾼다.
    for pos in range(len(answer)):
        row = answer[pos][0]
        col = answer[pos][1]
        board[row][col] = '.'
        for idx in range(4):
            nr = row + dx[idx] * answer[pos][2]
            nc = col + dy[idx] * answer[pos][2]
            board[nr][nc] = '.'
    # sum(board, [])를 하면 1차원 배열로 바뀌고 그 안 * 이 있는지 찾는다.
    if '*' not in sum(board, []) and len(answer) != 0:
        print(len(answer))
        for ans in answer:
            print(ans[0] + 1, ans[1] + 1, ans[2])
    else:
        print(-1)

Idea

1. 각 모서리에 * 이 있으면 십자가만으로 해당 격자판을 만들 수 없다.
2. 문제에서는 시작을 (1, 1)로 규정했지만 코드를 짤 때는 (0, 0) 에서 시작하는 것으로 한다.
3. 십자가를 찾을 때 최대 크기는 (i, j) 에서 상하좌우 공백 중 가장 짧은 것을 기준으로 한다.
4. size가 1인 십자가가 아닌 경우에는 더 큰 size의 십자가는 만들어 질 수 없다.
5. 찾은 십자가로 격자판을 만들 수 있는가는 두 가지 방법으로 할 수 있다.
   1. 같은 크기의 새로운 배열을 만들어 십자가를 찾을 때마다 해당 위치의 배열 값을 바꾸어준다.
   2. 찾은 십자가 위치를 모두 *이 아닌 다른 문자(여기서는 . )로 바꾸어주고 마지막에 * 이 존재하는지 확인한다.
6. sum(이차원 리스트, []) 를 하게 되면 일차원 리스트로 변환되어서 in 연산자를 사용하기 편해진다.

      ex) li1 = [[1, 2], [2, 4], [4, 8]] 인 경우에 li2 = sum(li1, [])를 하게 되면

           li2 = [1, 2, 2, 4, 4, 8] 이된다.