[SWEA][D4][#01861] 정사각형 방
작성:
업데이트:
카테고리: SWEA D4
태그: ProblemSolving, SWEA D4, SWEA PS
출처
학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.
문제
\({N}^{2}\)개의 방이 N×N형태로 늘어서 있다.
위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 \({N}^{2}\) 이하의 수 \({A}_{i,j}\)가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다.
당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다.
물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다.
처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (1 ≤ N ≤ 103)이 주어진다.
다음 N개의 줄에는 i번째 줄에는 N개의 정수 Ai, 1, … , Ai, N (1 ≤ \({A}_{i,j}\) ≤ \({N}^{2}\)) 이 공백 하나로 구분되어 주어진다.
Ai, 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
My Sol A : DFS 이용
def DFS(depth, ni, nj):
global mat
global max_depth, min_val
for di, dj in didj:
if (0<=ni+di<N) and (0<=nj+dj<N) and (mat[ni+di][nj+dj]==mat[ni][nj]+1):
DFS(depth+1, ni+di, nj+dj)
break
if max_depth > depth:
return
elif max_depth < depth:
max_depth = depth
min_val = mat[ni][nj]
elif max_depth == depth:
min_val = min(min_val, mat[ni][nj])
T = int(input())
for tc in range(1, T+1):
N = int(input())
didj = [(-1,0), (1,0), (0,1), (0,-1)]
mat = [list(map(int, input().split())) for _ in range(N)]
min_val = 0
max_depth = 1
for i in range(N):
for j in range(N):
DFS(1, i, j)
print(f'#{tc} {min_val-max_depth+1} {max_depth}')
NxN의 모든 점에 대해서 하나하나 완전 탐색하여 각 칸에서부터 상하좌우로 인접한 칸들의 값을 각각 확인하여 값이 1보다 큰 칸이 있다면 해당 칸부터 다시 상하좌우를 확인하는 방식이다. 재귀를 타고 들어가면 나머지 for문은 의미가 없으므로 break를 해준다.
DFS 특성상 어느 깊이까지 들어가는지 모르므로 for문이 끝나면 depth와 max_depth를 비교하여 처리하는 조건문을 한 번 확인해야 한다. 때문에 depth가 깊어지면 깊어질수록 불필요한 조건문을 계속 확인해야 하는 단점을 가진다.
2000ms의 연산시간이 필요했다.
My Sol B : BFS 이용
def BFS(depth, ni, nj):
global mat
global max_depth, min_lst
Q = [(depth, ni, nj)]
front = -1
end = 0
while front < end:
front += 1
depth, ni, nj = Q[front]
for di, dj in didj:
if not (0<=ni+di<N and 0<=nj+dj<N): continue
if mat[ni+di][nj+dj]!=mat[ni][nj]+1: continue
Q.append((depth+1, ni+di, nj+dj))
end += 1
break
if max_depth > depth:
return
elif max_depth < depth:
max_depth = depth
min_lst = [mat[ni][nj]]
elif max_depth == depth:
min_lst.append(mat[ni][nj])
T = int(input())
for tc in range(1, T+1):
N = int(input())
didj = [(-1,0), (1,0), (0,1), (0,-1)]
mat = [list(map(int, input().split())) for _ in range(N)]
min_lst = []
max_depth = 1
for i in range(N):
for j in range(N):
BFS(1, i, j)
min_val = min(min_lst) - max_depth + 1
print(f'#{tc} {min_val} {max_depth}')
DFS와 비슷하지만 depth마다 max_depth와 depth를 확인하는 것이 아닌, 각 칸에 대한 완전 탐색마다 한 번씩만 max_depth를 비교하는 방식이다. 하지만 마찬가지로 벡터를 이용해 상하좌우의 좌표의 값을 현재 좌표의 값과 비교해서 1 차이나는지 확인해야 하기 때문에 속도가 다소 느리다.
recursion이 깊어지지 않고, 매 depth마다 확인하는 과정을 제거하여서 900ms대의 조금 더 빠른 연산 시간을 보여주었다.
Sol C : 해시 사용
T = int(input())
for tc in range(1, T+1):
N = int(input())
mat = [list(map(int, input().split())) for _ in range(N)]
pos = [0]*(N*N+1)
pos[0] = (-1, -1)
for i in range(N):
for j in range(N):
pos[mat[i][j]] = (i, j)
cnt = [0]*(N*N+1)
cnt[N*N] = 1
for k in range(N*N, 0, -1):
x1, y1 = pos[k]
x2, y2 = pos[k-1]
d = abs(x1-x2 + y1-y2)
cnt[k-1] = cnt[k]+1 if d==1 else 1
max_v = 0
max_i = 0
for i, v in enumerate(cnt):
if max_v < v:
max_v = v
max_i = i
print(f'#{tc} {max_i} {max_v}')
어차피 N이 최대 1000이고, 값은 최대 NxN을 넘지 않으므로 1000x1000+1 만큼의 인덱스를 가지는 배열을 만들어서 각 좌표의 값을 인덱스로 하는 배열에 좌표의 정보를 저장하여 사용하는 방식이다.
좌표 배열인 pos와 같은 크기의 cnt 배열을 만들어주었다. 그리고 인덱스의 마지막인 NxN부터 처음까지의 좌표를 하나하나 확인하는데, 시작하는 cnt의 인덱스의 값은 1이다. 만약 두 좌표 사이의 거리가 1이면 이전 인덱스의 칸에 +1을 한 값을 넣고, 1이 넘는다면 다시 1을 채워 그 점부터 시작하는 것이다.
이렇게 모든 cnt를 채우고 최댓값을 가지는 가장 작은 인덱스를 출력하면 되겠다.
좌표를 저장해야 하기 때문에 처음에 2차원 배열 정보를 입력받고서 이를 하나하나 돌며 좌표를 저장하는 처리를 해야하지만, DFS나 BFS를 이용할 때처럼 각 칸마다 완전탐색하며 확인했던 좌표를 또 확인하는 과정이 필요없기 때문에 훨씬 빠르다.
결과
PASS
댓글남기기