정사각형 방 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 1861

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

N^2개의 방이 N×N형태로 늘어서 있다. 위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N^2 이하의 수 A(i,j)가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다. 당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다. 물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다. 처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라.

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (1 ≤ N ≤ 10^3)이 주어진다. 다음 N개의 줄에는 i번째 줄에는 N개의 정수 A(i), 1, … , A(i), N (1 ≤ A(i, j) ≤ N^2) 이 공백 하나로 구분되어 주어진다. A(i, j)는 모두 서로 다른 수이다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 한 칸을 띄운 후, 처음에 출발해야 하는 방 번호와 최대 몇 개의 방을 이동할 수 있는지를 공백으로 구분하여 출력한다. 이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력한다.

예시

입력	출력
2 2 1 2 3 4 3 9 3 4 6 1 5 7 8 2	#1 1 2 #2 3 3

---

2. 문제풀이

각 방마다 번호가 있고 상하좌우로 이동할때 현재위치에서 +1인방으로만 갈수있을때 제일 많이 이동할 수 있는 횟수가 몇 회인가를 찾는 문제이다. N이 크기는 하지만 +1로만 이동이 가능하기때문에 조건을 설정한다면 dfs로도 충분히 통과가 가능하다. 시작 위치에 따라 최대 횟수가 다를 수 있으므로, 반복문을 이용하여 각 위치별로 돌려본다. 나는 dfs와 비슷하게 동작하는 for문을 이용하여 만들었다. 이동이 가능하다면 새로운 리스트에 몇번에서 몇번이 이동이가능하다고 체크를 해줬다. 나중에 따로 반복문을 돌면서 연속적으로 True가 나오는 부분을 체크하며 제일 큰값을 찾았다.

 

---

3. 소스코드

#D4 1861 정사각형 방
 
#상 하 좌 우
move_list = [(-1,0), (1, 0), (0, -1), (0, 1)]
 
T = int(input())
for t in range(1, T+1):
    N = int(input())
    map_list = [list(map(int, input().split()))for _ in range(N)]
    #옆으로 이동이 가능한지 체크하는 변수
    check_list = [False] * (N*N + 1)
    minnum = max_count = count = 0
    for i in range(N):
        for j in range(N):
            #상하좌우를 이동해보며 이동이 가능한지 확인한다.
            for dy, dx in move_list:
                t_y = i+dy
                t_x = j+dx
                #이동이 불가능하다면 다른방향을 확인한다.
                if t_y <0 or t_x <0 or t_y >=N or t_x >= N:
                    continue
                #이동이 가능하다면 자신보다 1이큰지 확인한다.
                #크다면 정지하고 다음을 확인
                if map_list[t_y][t_x] == map_list[i][j] + 1:
                    check_list[map_list[i][j]] = True
                    break
    #연결되어있는 배열을 확인한다.
    for i in range(N*N-1, -1, -1):
        #연결이 되어있다면 카운트 증가
        if check_list[i]: count += 1
        #연결이 끊겼다면 지금까지 누적된 카운트를 체크한다.
        elif count :
            #최대 카운트보다 크다면 갱신하고 카운트 초기화
            if max_count <= count:
                max_count = count
                minnum = i+1
            count = 0
                
    print("#{} {} {}".format(t, minnum, max_count+1))