[SWEA/D3] 13732 정사각형 판정 (2시간 풀고 Pass..) / BFS, 이중 for문 한줄로 작성하기

문제 바로가기

SW Expert Academy

나의 코드 및 설명 01 (TC 20개 중 15개 성공)

• "#"가 존재하는 가로와 세로를 한 번에 찾아보려고 했으나 실패했다. 

def check_rec(board):
    global ans, garo_cnt, sero_cnt
    start_x,start_y = -1,-1
    #첫 번째로 "#"이 등장할 때의 x,y 좌표를 구한다
    for y in range(n):
        for x in range(n):
            if board[y][x] == "#":
                start_y = y
                start_x = x
                break
        if start_x != -1 and start_y != -1:
            break
    #첫 번째로 "#"이 등장한 y축의 "#"개수를 저장한다.            
    a = board[start_y].count("#")
    sero_cnt = 0
    #y축의 "#"개수 만큼 반복을 수행한다.
    for y in range(start_y,start_y+a):
        garo_cnt = 0
        for x in range(start_x,n):
            #범위 내에서 "#"이 등장할 때 마다 garo_cnt의 값을 1씩 증가시킨다.
            if board[y][x] == "#":
                garo_cnt += 1
            else:
                break
        sero_cnt += 1
        #y축의 "#"의 개수가 garo_cnt의 값과 다르다면, "#"은 붙어있지 않고 떨어져 있다.
        #따라서 정사각형이 될 수 없다.
        if board[y].count("#") != garo_cnt:
            ans = -1
            break
    if sero_cnt == garo_cnt and ans == 0:
        ans = 1
    else:
        ans = -1
        
t = int(input())

for test_case in range(1, t+1):
    n = int(input())
    board = []
    ans = 0
    garo_cnt = 0
    sero_cnt = 0
    for _ in range(n):
        board.append(list(input()))
    check_rec(board)
    if ans == 1:
        print("#{} {}".format(test_case, "yes"))
    else:
        print("#{} {}".format(test_case, "no"))

나의 코드 및 설명 02 (TC 20개 중 16개 성공)

• 생각을 바꾸어, "#"가 처음으로 존재할 때의 x,y 좌표를 구하고, 해당 열(y축)의 <"#"개수>를 저장받아 해당 x,y좌표를 기준으로 <저장한 "#"의 개수>만큼 반복을 수행해, 저장된 <"#"의 개수>와 일치하는지 확인한다.

## TC 20개 중에 16개 Pass
def check_rec(board):
    start_y,start_x = -1, -1
    ans = 0
    #첫 번째로 "#"이 등장할 때의 x,y 좌표를 구한다.
    for y in range(n):
        for x in range(n):
            if board[y][x] == "#":
                start_y = y
                start_x = x
                break
        if start_y != -1 and start_x != -1:
            break
    ##y축을 살펴본다.    
    #첫 번째로 "#"이 등장한 y축의 "#" 개수를 저장한다.
    a = board[start_y].count("#")
    #첫 번째로 "#"이 등장한 y축부터, "#"의 개수만큼 반복을 수행하는데
    for y in range(start_y, start_y+a):
        #이 때, y축에 해당하는 "#"의 개수가 서로 다르다면
        if board[y].count("#") != a:
            #ans에 -1을 저장하고
            ans = -1
            #반복문을 그 즉시 탈출한다.
            break

    ##x축을 살펴본다.
    cnt = 0
    #첫 번째로 "#"이 등장한 x축의 "#"의 개수만큼 반복을 수행하는데
    for x in range(start_x, start_x+a):
        cnt = 0
        #x축은 가만히 있고 y축을 변동시키며 x축에 "#"가 몇 개 있는지 센다.
        for y in range(n):
            if board[y][x] == "#":
                cnt += 1
        #만약 저장된 "#"의 개수와 다르다면
        if cnt != a:
            #ans에 -1을 저장하고 반복문을 그 즉시 탈출한다
            ans = -1
            break
    #모든 반복을 수행하고 나서 ans가 -1이 아니라면 참이다.    
    if ans == 0:
        return True
    else:
        return False

t = int(input())

for test_case in range(1, t+1):
    n = int(input())
    board = []
    for _ in range(n):
        board.append(list(input()))
    if check_rec(board) == True:
        print("#{} {}".format(test_case, "yes"))
    else:
        print("#{} {}".format(test_case, "no"))

나의 코드 및 설명 03 (Pass)

• 한 가지 간과한 것이 있었다. 예를 들어,
  #..
  .##
  .##
  일 경우엔 거짓인데, 02번 코드는 참의 값이 출력된다.
  문제를 보면 막혀있는 칸들이 '하나의' 정사각형을 이루는지 확인을 해야한다. 따라서 위의 경우는 첫 번째 #는 정사각형이지만, 정사각형이 두 개 생기게 되므로 거짓이 출력되도록 코드를 수정해야 한다.
  이것을 깨닫고 다음과 같이 코드를 수정하고 Pass를 받을 수 있었다.

def check_rec(board):
    start_y,start_x = -1, -1
    ans = 0
    total_cnt = 0
    #추가한 부분 "#"의 개수를 체크함으로써 하나의 정사각형이 완성되는지 확인한다.
    for y in range(n):
        total_cnt += board[y].count("#")
    for y in range(n):
        for x in range(n):
            if board[y][x] == "#":
                start_y = y
                start_x = x
                break
        if start_y != -1 and start_x != -1:
            break
    a = board[start_y].count("#")
    for y in range(start_y, start_y+a):
        if board[y].count("#") != a:
            ans = -1
            break
    cnt = 0
    for x in range(start_x, start_x+a):
        cnt = 0
        for y in range(n):
            if board[y][x] == "#":
                cnt += 1
        if cnt != a:
            ans = -1
            break
    #추가한 부분 
    if ans == 0 and a*a == total_cnt:
        return True
    else:
        return False

t = int(input())

for test_case in range(1, t+1):
    n = int(input())
    board = []
    for _ in range(n):
        board.append(list(input()))
    if check_rec(board) == True:
        print("#{} {}".format(test_case, "yes"))
    else:
        print("#{} {}".format(test_case, "no"))

다른 코드 및 설명 (BFS를 활용한 풀이)

• BFS(큐)를 활용한 풀이 방법이다.
  먼저 큐 <square>에 board의 x,y좌표 값이 "#"인 x,y좌표를 저장한다. 그 후, 생성된 bfs 함수를 실행시켜 결과를 출력한다.
• bfs(sqaure, board):
  정사각형의 넓이는 <변의 길이**2>이다. 이를 통해 len(square) ** 0.5 를 통해 "#"의 길이 즉, 정사각형의 변이 되는 길이를 구할 수 있다. 이 때 변의 길이가 1로 나누어 떨어지지 않는다면, 정사각형이 아니다.
  그 후, "#"인 좌표를 저장한 큐 <square>의 제일 왼쪽에 저장된 좌표(첫 번째 "#"이 되는 좌표)를 꺼내어 하나씩 살펴본다. 만약 좌표 값이 "#"이 아니라면 "no"를 리턴한다. 반복문이 끝까지 수행되었을 때는 "yes"를 리턴한다. 

from collections import deque

def bfs(square, board):
    len_sq = len(square) ** 0.5
    #정사각형이 이루어질 수 있는 개수가 아니다
    if len_sq % 1 != 0:
        return "no"
    x,y = square.popleft()
    for i in range(y, y+int(len_sq)):
        for j in range(x, x+int(len_sq)):
            if board[i][j] != "#":
                return "no"
    return "yes"
            

t = int(input())
for test_case in range(1, t+1):
    board = []
    n = int(input())
    for _ in range(n):
        board.append(list(input()))
    square = deque((x,y) for y in range(n) for x in range(n) if board[y][x] == "#")
    answer = bfs(square, board)
    
    print("#{} {}".format(test_case, answer))

피드백

DFS 혹은 BFS를 통해 문제를 해결하고 싶었지만, 구현하는 게 어려워 단순 구현으로 문제를 해결하였다. 2시간 넘게 소요되었다. 그래도 문제를 해결해서 너무 뿌듯했다.

다른 사람의 코드를 보고 BFS를 활용한 풀이를 확인할 수 있었는데, 풀이 과정을 보니 내가 단순 구현으로 푼 과정과 전체적인 맥락은 비슷하다. (첫 번째로 "#" 가 오는 좌표부터 정사각형의 변의 길이가 되는 "#"의 길이만큼 반복문을 수행하고, 하나라도 "#"가 아닌 값이 온다면 "no"를 리턴한다.)

개인적으로 너무 어려웠던 문제이다. DFS, BFS 문제도 여러 번 풀어보아야 할 것 같다.