[백준/2658] 직각이등변삼각형찾기 (Python)

Problem : https://www.acmicpc.net/problem/2658

2658번: 직각이등변삼각형찾기

Difficulty : Gold 1

 

Status : Solved

 

Time : 01:54:13

 

---

 

문제 설명

 

 

가로 10줄, 세로 10줄에 1 또는 0이 적혀진 배열이 있다. 이러한 배열 안에 있는 숫자 1들이 만드는 모양이 한 개의 직각이등변삼각형인지 아닌지 알아내는 프로그램을 작성하시오.

직각이등변삼각형의 적어도 한 변은 수평선 또는 수직선이다. 단, 직각이등변삼각형의 내부도 1로 채워져 있어야 한다. 입력된 모양은 삼각형이 아닐 수 있다.

 

 

입력 및 출력

 

입력

입력은 10줄로 이루어지며 각 줄은 첫 칸부터 공백없이 10개의 0또는 1로 이루어진다.

 

출력

입력된 모양이 직각이등변 삼각형을 이루는 경우에는 세 꼭짓점의 위치를 출력하고, 그렇지 않은 경우에는 0을 출력한다. 각 꼭짓점의 위치를 한 줄에 두 개의 수로 출력한다. 두 수는 하나의 빈 공백을 두고 출력한다. 첫째 수는 그 꼭짓점이 위에서부터 몇 번째 줄에 있는가 나타내며, 두 번째 수는 왼쪽부터 몇 번째 칸에 있는가를 나타내야 한다. 꼭짓점을 출력할때는 첫째 수가 작은 것부터, 첫째 수가 같을 경우 두 번째 수가 작은 것부터 출력한다.

 

입력 예시

0000000000
0000001000
0000011000
0000111000
0001111000
0000111000
0000011000
0000001000
0000000000
0000000000

 

출력 예시

2 7
5 4
8 7

 

 

---

 

풀이

 

수많은 맞왜틀로 인해 1시간을 더 허비했던 문제... min, max 값 순서가 반대가 되어 벌어진 문제였다. 문제 자체는 단순한 구현이다.

 

• find_rectangle : 삼각형을 꼭지점을 변으로 하는 직사각형을 찾는다. 좌표값이 1인 x, y좌표중 최대, 최소 값을 반환한다.
• find_all_vertexs : 삼각형의 모든 꼭지점은 맞닫는 직사각형의 변 위에 존재하게 된다. 즉, 변 위를 모두 탐색하여 꼭지점을 반환하면 된다. 삼각형의 변과 직사각형의 변이 겹칠 경우, 양 끝값(x, y좌표중 최댓값과 최솟값)을 반환하면 된다.
• square_length : 두 꼭지점의 좌표가 주어졌을 때, 두 꼭지점간의 거리의 제곱값을 반환한다.
• is_correct : 꼭지점만을 탐색하면 삼각형이 아닌 경우, 삼각형이 두 개 이상일 경우, 혹은 내부가 빈 삼각형인 경우에 대해 오답이 발생한다. 따라서 이들 경우의 수를 따져야 한다.
  • y좌표를 기준으로 x좌표가 1인 값인 좌표들을 구한다. 이 중 최솟값과 최댓값의 차가 총 좌표의 개수와 일치해야 한다(그렇지 않으면 1 내부에 0이 있다는 이야기가 된다). 만약 일치한다면 그 길이를 저장한다.
  • 이렇게 구해진 길이 리스트의 최댓값을 중심으로 양 끝까지 탐색한다. 정다각형이라면 같은 등차로 계속 감소해나갈 것이며, 삼각형의 경우 길이 등차는 최대 2개가 된다. 만약 탐색 도중 다른 등차를 만난다면 삼각형이 아니라는 의미이다.
• is_irt : 구해진 세 꼭지점을 토대로 직각이등변삼각형 여부를 반환한다. 만약 꼭지점 리스트의 길이가 3이 아니라면 삼각형이 아니란 의미이다. 직각이등변삼각형은 빗변을 제외한 두 변의 길이가 같고 피타고라스의 정리를 만족하므로 이를 검사한다.
• solve : 메인함수. find_rectangle로 직사각형 여부를 판별하고(만약 최대, 최소값이 제대로 나오지 않으면 빈 공간이란 의미이다), find_all_vertexs 함수로 이들의 꼭지점 리스트를 얻는다. 그리고 is_correct 함수와 is_irt 함수로 직각이등변삼각형인지 여부를 판별하여 그에 따라 값을 출력한다.

 

 

 

풀이 코드

map_list = [input().strip() for _ in range(10)]

def find_rectangle() :
  min_x, min_y = 10, 10
  max_x, max_y = -1, -1

  for i in range(10) :
    for j in range(10) :
      if map_list[i][j] == '1' :
        min_x = min(min_x, j)
        max_x = max(max_x, j)
        min_y = min(min_y, i)
        max_y = max(max_y, i)

  return (min_x, max_x), (min_y, max_y)

def find_all_vertexs(x_tuple, y_tuple) :
  result = set()
  
  for j in x_tuple :
    tmp = list()
    for i in range(10) :
      if map_list[i][j] == '1' :
        tmp.append((i+1, j+1))
    if tmp :
      result.add(tmp[0])
      result.add(tmp[-1])

  for i in y_tuple :
    tmp = list()
    for j in range(10) :
      if map_list[i][j] == '1' :
        tmp.append((i+1, j+1))
    if tmp :
      result.add(tmp[0])
      result.add(tmp[-1])

  result = list(result)
  result.sort()
  
  return result

def square_length(a, b) :
  return (a[0] - b[0])**2 + (a[1] - b[1])**2

def is_correct(x_tuple, y_tuple) :
  min_x, max_x = x_tuple
  min_y, max_y = y_tuple

  len_list = list()
  for i in range(min_y, max_y+1) :
    tmp = list()
    for j in range(min_x, max_x+1) :
      if map_list[i][j] == '1' :
        tmp.append(j)
    if tmp :     
      if len(tmp) != tmp[-1] - tmp[0] + 1 :
        return False
      len_list.append(len(tmp))

  if not len_list :
    return False
    
  max_idx = len_list.index(max(len_list))
  if max_idx > 0 :
    upper_diff = len_list[max_idx] - len_list[max_idx-1]
    for i in range(max_idx) :
      if len_list[i+1] - len_list[i] != upper_diff :
        return False

  if max_idx < len(len_list) - 1 :
    lower_diff = len_list[max_idx] - len_list[max_idx+1]
    for i in range(max_idx, len(len_list)-1) :
      if len_list[i] - len_list[i+1] != lower_diff :
        return False

  return True

def is_irt(vertex_list) :
  if len(vertex_list) != 3 :
    return False
    
  a, b, c = vertex_list
  line_list = [ square_length(a, b), square_length(b, c), square_length(c, a) ]
  line_list.sort()
  
  return line_list[0] == line_list[1] and line_list[0] + line_list[1] == line_list[2]


def solve() :
  x_tuple, y_tuple = find_rectangle()
  if x_tuple == (10, -1) :
    print(0)
    return
  
  vertex_list = find_all_vertexs(x_tuple, y_tuple)

  if is_irt(vertex_list) and is_correct(x_tuple, y_tuple) :
    for vertex in vertex_list :
      print(*vertex)
  else :
    print(0)

solve()

풀이 완료!