18242번 - 네모네모 시력검사

문제 : https://www.acmicpc.net/problem/18242

문제(요약)

이차원 배열에서 단 하나의 정사각형이 존재하고, 해당 정사각형에서 네 변 중 한 변의 가운데만 뻥 뚫려있다. 뻥 뚫려있는 변의 위치를 출력하는 문제이다!

풀이

1. 보드(이차원 배열)에서 정사각형을 먼저 찾는다.
2. 정사각형에서 뚫린 변의 위치를 찾는다.

1번 순서

• 우선 이차원 배열에서 색칠된 부분을 찾아 배열(rectangle_coords)에 (x, y) 형태로 저장한다.
• 이차원 배열을 모두 탐색했으면 rectangle_coords 를 정렬하여 왼쪽 위 좌표와, 오른쪽 아래 좌표를 구한다.
• 왼쪽 위 좌표와, 오른쪽 아래 좌표를 이용하여 정사각형의 네 꼭짓점 좌표를 모두 구한다.

2번 순서

• 아래 순서대로 탐색하며 색칠이 안된 곳을 찾는다.
  - 오른쪽 위 좌표부터 오른쪽 아래 좌표까지 탐색하여 찾으면 RIGHT 을 출력한다.
  - 왼쪽 위 좌표부터 왼쪽 아래 좌표까지 탐색하여 찾으면 LEFT 을 출력한다.
  - 왼쪽 위 좌표부터 오른쪽 위 좌표까지 탐색하여 찾으면 UP 을 출력한다.
  - 왼쪽 아래 좌표부터 오른쪽 아래 좌표까지 탐색하여 찾으면 DOWN 을 출력한다.

code

import sys

input = sys.stdin.readline

def solution():
    N, M = map(int, input().split())
    board = []
    for _ in range(N):
        board.append(input())

    len_y = N
    len_x = M
    rectangle_coords = []

    for i in range(len_y):
        for j in range(len_x):
            if board[i][j] == '#':
                rectangle_coords.append([j, i])
    left_top_coord = sorted(rectangle_coords, key=lambda x: [x[0], x[1]])[0]
    right_bottom_coord = sorted(rectangle_coords, key=lambda x: [-x[0], -x[1]])[0]
    right_top_coord = [right_bottom_coord[0], left_top_coord[1]]
    left_bottom_coord = [left_top_coord[0], right_bottom_coord[1]]

    if search(board, right_top_coord, right_bottom_coord):
        print('RIGHT')
    if search(board, left_top_coord, left_bottom_coord):
        print('LEFT')
    if search(board, left_top_coord, right_top_coord):
        print('UP')
    if search(board, left_bottom_coord, right_bottom_coord):
        print('DOWN')


def search(board, start_coord, end_coord):
    start_x, start_y = start_coord
    end_x, end_y = end_coord

    if start_y == end_y:
        for x in range(start_x, end_x):
            if board[start_y][x] != '#':
                return True
    if start_x == end_x:
        for y in range(start_y, end_y):
            if board[y][start_x] != '#':
                return True
    return False


if __name__ == "__main__":
    solution()

result

오랜만에 백준 알고리즘 풀었더니 어떻게 제출하는지 까먹음...