[ETC] SWEA : 13732_정사각형 판정

[inseonyun]

Source URL : SWEA : 13732_정사각형 판정

문제 요구사항 :

• N×N 크기의 격자판이 있다. 각각의 격자는 비어 있거나(‘.’), 막혀 있다(‘#’). 이때, 막혀 있는 칸들이 하나의 정사각형을 이루는지를 판단하는 프로그램을 작성하라.

[입력]

• 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
• 각 테스트 케이스의 첫 번째 줄에는 격자판의 크기 N (1≤N≤20 이 주어진다.
• 다음 N개의 줄은 격자판의 배치를 나타내며, 각 줄에는 ‘.’ 또는 ‘#’로만 이루어진 길이가 N인 문자열이 주어진다.
• 모든 격자판에는 최소 1개 이상의 ‘#’ 칸이 있음이 보장된다.

[출력]

• 각 테스트 케이스마다 격자판의 막혀 있는 칸들이 하나의 정사각형을 이루면 ‘yes’를, 그렇지 않다면 ‘no’를 출력한다.

접근 방법 :

• 문제를 잘못 이해해서 BFS로 접근했다. 문제에 나와있는 TC 2번을 보면 '#'이 각각 1개씩 네 군데에 떨어져있는데, 이게 나는 문제에서 원하는 정사각형 하나가 아닌 4개여서 틀렸다고 판단하고 문제를 풀었는데 아니었다.
• 문제에서 요구하는 것은 '#'이 나오게 되면 그게 바로 사각형의 시작점이 된다. 그럼 그 후로 나오는 '#'들을 이었을 때 이게 정사각형이냐를 판별하는 문제였다.
• 즉, BFS로 굳이 풀 필요 없다. 탐색만으로 충분히 가능하다

풀이 순서 :

1. TC를 입력받아 해당 TC만큼 test_case를 반복한다.
2. N을 입력받고, N 크기만큼의 맵 정보를 입력 받는다.
3. 맵을 탐색하며, '#'이 나왔을 때 사각형의 좌상단 좌표, 우하단 좌표를 min, max 함수를 이용해서 찾는다.
4. 해당 좌표를 x2 - x1 값과 y2 - y1의 값이 같지 않다면 false ( no 출력)을, 같다면 x1부터 x2까지, y1부터 y2까지 for문을 돌려 빠짐없이 '#'으로 채워졌는지 확인한다. 안 채워져있다면 return false
5. 앞 조건식에서 return 되지 않고 진행됐다면 return true를 한다.

[inseonyun]

문제 풀이 결과 :