[SWEA] D4 1861 정사각형방 (Python)

출처

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

 

문제

N2개의 방이 N×N형태로 늘어서 있다.

위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N2 이하의 수 Ai,j가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다.

당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다.

물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다.

처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (1 ≤ N ≤ 103)이 주어진다.

다음 N개의 줄에는 i번째 줄에는 N개의 정수 Ai, 1, … , Ai, N (1 ≤ Ai, j ≤ N2) 이 공백 하나로 구분되어 주어진다.

Ai, j는 모두 서로 다른 수이다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

한 칸을 띄운 후, 처음에 출발해야 하는 방 번호와 최대 몇 개의 방을 이동할 수 있는지를 공백으로 구분하여 출력한다.

이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력한다.


[예제 풀이]

첫 번째 테스트 케이스는 1 또는 3이 적힌 곳에 있어야 한다.

두 번째 테스트 케이스는 3 또는 6이 적힌 곳에 있어야 한다.

 

2 2 1 2 3 4 3 9 3 4 6 1 5 7 8 2

#1 1 2 #2 3 3

풀이

첫번째는 그냥 반복문을 활용해 각 x,y에 대해서 완전 탐색하였다. 각 위치에서 상,하,좌,우로 갈 수 있는지 판단하였고 갈 수 있다면 cnt를 하나씩 늘려줬으며 최종적으로 한 위치에서 상하좌우로 갈 수 없게 될 때까지가 탐색을 하였다.

두번째는 BFS를 활용해서 풀어보았다. 시작 위치를 queue에 집어넣고 pop을 한후 역시 4방향을 탐색하여 갈 수 있다면 queue에 append하였고 queue가 빌때까지 탐색하였다.

 

코드

반복문 활용

def iswall(x,y): # 벽 체크 맵의 범위안에 있는지 + 다음칸과의 차가 1인지
    if (0 <= x < n) and (0 <= y < n) and (arr[x][y] - arr[x-dx[i]][y-dy[i]] == 1):
        return False
    return True 
 
T = int(input())
for t in range(T):
    n = int(input())
    arr = []
    for _ in range(n):
        arr.append(list(map(int,input().split())))
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    max_cnt = 0 # 결과값 / 이동한 방의 최대 개수가 저장될 변수
    room = 9999999 # 결과값 2 / 시작 방번호가 저장될 변수
    for x in range(n): # 모든 x,y 탐색
        for y in range(n):
            init_x = x # x와 y가 탐색을 하며 변동 되므로 최초 위치를 따로 저장함. 나중에 cnt와 room 비교를 위해 필요함
            init_y = y
            cnt = 1
            idx = 0 # for문 돈 횟수 
            i = 0
            while 1:
                if idx > 4: # 현재 위치에서 4방향을 다 돌고도 갈 곳이 없다면 종료
                    break
                if iswall(x+dx[i],y+dy[i]) == False: 
                    x+=dx[i]
                    y+=dy[i]
                    cnt += 1
                    idx = 0 # 벽체크 후 갈 수 있다면 한칸 간 후 다시 4방향 체크를 할 것이기에 0으로 초기화
                    i = 0
                else:
                    i += 1 
                    idx += 1
                if i == 4:
                    i = 0
            if cnt > max_cnt:
                max_cnt = cnt
                room = arr[init_x][init_y]
            elif cnt == max_cnt:
                if room > arr[init_x][init_y]:
                    room = arr[init_x][init_y]
    print('#{} {} {}'.format(t+1,room,max_cnt))
          

BFS 활용

dx = [0,1,0,-1]
dy = [1,0,-1,0]
 
T = int(input())
for t in range(T):
    N = int(input())
    mapp=[]
    max_cnt = 0 # 결과값 / 이동한 방의 최대 개수가 저장될 변수
    room = 999999999999 # 결과값 2 / 시작 방번호가 저장될 변수 
    for _ in range(N):
        mapp.append(list(map(int,input().split())))
    for x in range(N): # 모든 x,y 탐색
        for y in range(N):
            cnt = 1 
            q = [(x,y)] # 첫 시작 방 위치 queue에 저장
            while q: # BFS 탐색 시작 / q가 빌 때까지 q의 요소를 pop 해서 4방향 탐색 조건 만족시 append
                qq = q.pop()
                for i in range(4):
                    if 0 <= qq[0] + dx[i] < N and 0 <= qq[1] + dy[i] < N and (mapp[qq[0]+dx[i]][qq[1]+dy[i]] - mapp[qq[0]][qq[1]] == 1):
                        cnt += 1
                        q.append((qq[0]+dx[i],qq[1]+dy[i]))
            if cnt > max_cnt: # 탐색 종료 후 건너온 방의 개수가 현재까지 저장된 최대 방 건너온 개수와 비교해서 더 많다면
                max_cnt = cnt # cnt가 이제 최대 방 건너온 개수가 됨
                room = mapp[x][y] # room에 위치 저장
            elif cnt == max_cnt: # 건너온 개수가 같다면
                if mapp[x][y] < room: # 저장된 방 번호와 비교해 작은지 판단
                    room = mapp[x][y]
 
    print('#{} {} {}'.format(t+1,room, max_cnt))