[Python] 백준 3050번: 집들이

https://www.acmicpc.net/problem/3050

3050번: 집들이

 

 > 접근

처음 예제 입력 2를 보고, 모든 지점에 대해서 시계 방향 또는 반시계 방향으로 돌아서 직사각형의 width, height를 알아낼 수 있다고 생각했다. 대략 아래와 같이 말이다.

하지만 아래의 레이아웃에 대해서는 전혀 먹히지 않았다는 것을 알았다.

 

 

이에 따라 다른 방법을 고안해냈다. 특정 지점을 잡고 그곳에서의 직사각형들을 전부 구해내는 것인데, 사진으로 묘사하면 다음과 같다.

 get_people_count_for_table(x_start, y_start)

즉, row단위로 직사각형을 구하는 것이다. 이 때 중요한 특징은 width에 대해 다음과 같은 식이 성립한다는 점이다.

width = min(width, '해당 row에서의 width')

이런 내용의 함수(get_people_count_for_table())를 (0,0)~(R-1,C-1)까지 돌려주면 원하는 결과가 나오게 된다.

 

위에서 '해당 row에서의 width'를 사전에 모두 구해줌으로써 더 효율적인 풀이가 가능해진다. set_width_to_rightside() 함수를 통해 width_to_rightside라는 리스트를 초기화해준 뒤에 값을 구해주었다.

 

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

def solution():
  global width_to_rightside
  res = 0

  width_to_rightside = [[0]*C for _ in range(R)]
  set_width_to_rightside()

  for i in range(R):
    for j in range(C):
      res = max(res, get_people_count_for_table(i, j))

  return res

def set_width_to_rightside():     
  global width_to_rightside

  for i in range(R):
    j = 0
    while(j<C):
      if(layout[i][j] == '.'):
        width = get_width_to_rightside(i, j)

        # . . . . . 에서 5를 구했으므로 아래와 같이 처리해준다.
        # 5 4 3 2 1
        while(width > 0):
          width_to_rightside[i][j] = width

          width -= 1
          j += 1
      else:     
        j += 1

def get_width_to_rightside(x, y):
  # (x, y) -> (x, C)
  for j in range(y, C):
    if(layout[x][j] == 'X'):
      j -= 1
      break                        

  return j - y + 1

def get_people_count_for_table(x_start, y_start):
  if(layout[x_start][y_start] == 'X'): return 0 
  
  global width_to_rightside         
  res = 0

  # 테이블: (x_start, y_start) ~ (x_end, y_start + 'width - 1')  
  # 사전에 만들어둔 width_to_rightside을 통해, 특정 좌표에서
  # 오른쪽으로의 width를 바로 알 수 있다.      
  width = float('inf')
  for x_end in range(x_start, R):
    if(layout[x_end][y_start] == 'X'): break

    width = min(width, width_to_rightside[x_end][y_start])
    height = (x_end - x_start) + 1

    res = max(res, 2*width + 2*height - 1)
           
  return res        
    

if __name__ == '__main__':
  R, C = map(int, input().split())
  layout = [list(input().rstrip()) for _ in range(R)]
       
  print(solution())