Py) SWEA 13732 정사각형 판정

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX8BAN1qTwoDFARO& 

SW Expert Academy

 

1차: 1시간
2차: 20분

 

-1. 미리 얹는 피드백
1) 문제 이해를 잘못했다. 막힌 벽이 정사각형을 이루는지 판단하라 했을 때
#..#
....
....
#..# 이런것도 되는 줄 알았다. 테스트케이스를 제대로 보지 않은 내탓이다.
2) 이건 문제에서 명시가 제대로 안된 것 같다. 프로그래머스였다면 이런 부분도 문제 풀 때 민감하게 생각해야했을 것 같다.
#...
####
####
#### 이렇게 사각형을 이루는 #이 없을 수도 있는 경우. 어쨌든 정사각형을 이루니 이것도 되지 않을까? 생각했었다.

 

0. 입출력

 

1. 김예고리즘

1-1. 알고리즘
1) first와 last를 (21, 21)로 초기화. 처음 만난 #의 좌표를 first로 갱신해 저장. 그 다음 만난건 last
2) 해당 좌표들을 기준으로 행, 열에 각각 #이 있는지 확인, 없으면 no
-> 근데 이 경우, 내가 생각했던 2번 케이스는 no라고 하게 된다. (애초에 문제 이해를 잘못했지만?)
-> 또한 문제 이해를 잘못했으므로(꽉찬 정사각형만 된다는..) 정답이 나올 수 없는 풀이.

1-2. 코드
풀다 말긴 했지만 그래도 저장

T = int(input())
for i in range(1, T+1):
    size = int(input())
    tmap = [list(input().split()) for s in range(size)]
    # tmap = []
    # for k in range(size):
    #     tmap.append(list(input().split()))
    first = (21,21)
    last = (21,21)
    tmp = 'yes'
    for row in range(size):
        for col in range(size):     # 한줄 완성하고
            if tmap[row][col] == '#':
                if first == (21, 21):
                    first = (row, col)
                    break
                if first != (21, 21) and last == (21, 21):  # last 지정
                    last = (row, col)
        for search in range(0, size):
            if tmap[search][size] != '#':
                tmp = 'no'
                break
        for search2 in range(0, size):
            if tmap[size][search2] != '#':
                tmp = 'no'
                break

 

2. Solution

2-1. 사용 자료구조 및 알고리즘: x

2-2. 로직
1) 비어있는 2차원 리스트를 만들어 맵에서 #이 발견될때마다 해당 위치의 빈 리스트에 1을 저장한다. 동시에 #의 개수를 확인하는 용인 cnt에 1씩 올린다.
--1차 확인--
2) (check 함수에서) 1이 발견된 처음 좌표부터 발견되지 않을때까지 세로줄을 검사한다. -> down으로 발견 개수 표시
3) 가로줄도 검사한다 -> right 표시
4) down, right 개수가 일치하지 않다면 return no
--좀 더 세밀하게 2차--
5) 처음 발견된 좌표에서 마지막 발견까지 해당 정사각형을 확인한다. : 1인 경우 확인용 변수 cnt를 깎음
6) cnt가 남는다면 return no, 확인하던 중 중간에 1이 아닌 부분이 나온다면 return no

 

2-3. 코드

t = int(input())

def check(board, cnt, n):
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                down = 0
                right = 0
                for k in range(i+1, n):     # 1이 처음 발견된 곳 부터 나올때까지
                    if board[k][j]==1:      # 세로줄 검사
                        down += 1
                    else: break
                for k in range(j+1, n):
                    if board[i][k] == 1:    # 가로줄 검사
                        right +=1
                    else: break
                if down != right:
                    return 'no'
                
                for x in range(i, i+down+1):    # 발견된 곳까지 내려가서 검사
                    for y in range(j, j+right+1): # 옆으로 나가면서 검사
                        if board[x][y] ==1:
                            cnt -= 1
                        else: return 'no'
                
                if cnt != 0: return 'no'
                
                return 'yes'


for tc in range(1, t+1):
    n = int(input())
    board = [[0 for _ in range(n)]for _ in range(n)]   # 비어있는 2차원 list
    cnt = 0

    for i in range(n):
        data = list(map(str, input()))
        for j in range(n):    # 하나씩 찍히게 됨
            c = data[j]
            if c == '#':
                board[i][j]=1   # 1로 바꾸고, cnt를 올리고 이후 확인
                cnt+=1
            else:
                continue

    result = check(board, cnt, n)
    
    print('#%d %s' %(tc, result))

 

3. 피드백
1) solution으로 다시 풀면서 몇번의 시행착오를 거쳤다.

for l in range(j+1, n):

                    if board[i][l] == 1:

                        row += 1

                    else: break

i+1이라고 놔버린 것.

for a in range(i, i+col+1):

                    for b in range(j, j+row+1):

                        if board[a][b] == 1:

                            cnt -=1

                        else:

                            return 'no'

for문 둘다 i로 놔버림.

문제 풀면서 정사각형이니까 #이 발견되는 좌표의 x,y값이 같을거라고 생각했다. 그렇게 생각하기엔
.....
..###
..###
..###
..... 와 같은 경우가 있다. 이러면 (2, 1)에서 발견이니까 해당이 안됨.

2) 2차원 리스트 만들기 어렵다. 익숙해지면 외워질거 같다.

board = [[0 for i in range(n)] for j in range(n)]