[SWEA] 1861_정사각형 방

📕 문제

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

SW Expert Academy

 

💡 풀이법

1. 방문처리를 해줄 visited 라는 NxN 행렬을 만든다.

2. ans는 최대 방의 개수이고, 가장 많은 방을 이동할 수 있는 출발 방번호이고, max_ans는 현재 방위치에서 갈수 있는 최대 방 개수이다.

(즉, ans는 전체를 모두 봤을때 나온 최대 방의 개수이고, max_ans는 현재 위치에서만 갈수 있는 최대 방의 개수이다.)

3. bfs를 이용하는데 l은 현재까지의 방의 개수이다.

4. 이중 포문을 돌며 격자칸에 한칸씩 접근해서 방문하지 않은 칸이라면 bfs를 돌린다.

5. 사방을 탐색하며 벽이 아니고 현재 칸보다 1 크다면 deq에 추가한다.

6. 추가함과 동시에 방문처리를 해준다.

7. while문을 빠져나오면 l과  max_len을 비교해서 l이 더 크면 max_len을 l로 바꿔준다.

8. bfs 실행 후에 max_len과 ans를 비교해서 max_len이 더 크다면 ans를 바꿔주고, n도 현재의 방번호로 바꿔준다.

만약, max_len이 ans와 같은데 n이 현재의 방 번호보다 크다면 n을 현재의 방번호로 바꿔준다.

 

from collections import deque

def bfs(x, y, l):
    global max_len

    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    deq = deque()
    deq.append((x, y, l))
    visited[x][y] = 1

    while deq:
        x, y, l = deq.popleft()

        for dx, dy in dxy:
            nx, ny = x + dx, y + dy

            if -1 < nx < N and -1 < ny < N:
                if matrix[nx][ny] == matrix[x][y] + 1:
                    deq.append((nx, ny, l+1))
                    visited[x][y] = 1

    if l > max_len:
        max_len = l

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    visited = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                max_len = 0
                bfs(i, j, 1)
                if max_len > ans:
                    ans = max_len
                    n = matrix[i][j]
                elif max_len == ans and matrix[i][j] < n:
                    n = matrix[i][j]
    print('#{} {} {}'.format(tc, n, ans))