[SWEA 코딩] 정사각형 방 - PYTHON #1861

소스 코드

def bfs():
    global room_num
    global cnt

    temp = [[q,w]]

    temp_cnt = 1
    temp_num = room[q][w]

    while len(temp):
        i,j = temp.pop(0)

        for e in range(4):
            ii = i + x[e]
            jj = j + y[e]

            if 0 <= ii < n and 0 <= jj < n:
                if room[ii][jj] - room[i][j] == 1:
                    temp.append([ii,jj])
                    temp_cnt += 1
                    break

    if temp_cnt > cnt:
        cnt = temp_cnt
        room_num = temp_num

    elif temp_cnt == cnt:
        if room_num > temp_num:
            room_num = temp_num

    return

T = int(input())

x = [-1,1,0,0]
y = [0,0,-1,1]

for tc in range(1,1+T):

    # 방의 크기 n*n
    n = int(input())

    room = [list(map(int,input().split())) for _ in range(n)]

    room_num = 0
    cnt = 0

    for q in range(n):
        for w in range(n):
            if cnt < n*n-room[q][w]+1:
                bfs()

    print('#{} {} {}'.format(tc,room_num,cnt))

 

---

해결 방법

1. bfs 방식으로 접근

 

2. cnt < n*n-room[q][w]+1일 때에만 bfs 함수를 호출해서 연산 최소화

---

느낀 점

해결하고 나서 속도나 코드가 마음에 들지 않아서 확인해보니

 

bfs를 사용하지 않고도 해결할 수 있었다

 

그 방법을 보면서 익혀둘 필요가 있음

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.