728x90
반응형
이번 문제는 두 가지 방법으로 풀어보았다.
# 1차 시도
: 델타로 이동하며 완전탐색하는 알고리즘 구현. 패스는 했지만, 시간이 오래 걸리는 것이 단점, 중간에 자꾸 실수했던 부분은 처음 시작한 위치를 start라는 변수에 저장하는 과정을 놓쳐서 출력 조건 중 '이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력한다.' 조건을 충족하지 못했다.
추가적으로 아직까지 dfs 완전 탐색, 변수를 지정하고 활용하는 법이 서툴다고 느껴졌다. 앞으로 이 부분 더 추가로 문제 풀면서 보완해야겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for t in range(1,int(input())+1):
n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
res_cnt = -1
res_start = 0
for i in range(n):
for j in range(n):
tx = i
ty = j
start = arr[i][j]
cnt = 1
while True:
for k in range(4):
ni = tx+dx[k]
nj = ty+dy[k]
if (0<= ni <n and 0<= nj <n and arr[ni][nj] - arr[tx][ty] == 1):
tx = ni
ty = nj
cnt +=1
break
else:
break
if cnt > res_cnt:
res_cnt = cnt
res_start = start
elif cnt == res_cnt:
if res_start > start:
res_start = start
print('#{} {} {}'.format(t, res_start, res_cnt))
|
|
# 2차 시도
: sw 아카데미에서 다른 사람의 풀이 방법을 참고해 다시 풀어보았다.
[알고리즘 특징]
- 가장 큰 특징이 n*n까지의 수를 담은 리스트를 만들어 준 것
- 첫 포문에서 완전탐색으로 이동할 수 있는 모든 경우의 수를 구해놓고
- 그 다음 파트의 포문에서 최대 방 개수를 찾는 연산을 진행해 중복 계산을 피할 수 있다는 점
- 결과적으로 첫번째 시도의 방법 보다 계산 시간을 많이 줄일 수 있었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
for t in range(1, int(input())+1):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
n_lst = [0]*(n**2+1)
max_v = -1
for i in range(n):
for j in range(n):
for k in range(4):
if 0 <= i+dx[k] < n and 0<= j+dy[k] < n:
if arr[i+dx[k]][j+dy[k]] == arr[i][j] + 1:
n_lst[arr[i][j]] = 1
break
for i in range(1, n**2):
if n_lst[i] == 1 and n_lst[i-1] == 0:
cnt = 1
while True:
if n_lst[i+cnt] == 1:
cnt += 1
else:
break
if max_v < (cnt + 1):
max_v = cnt + 1
res_num = i
print('#{} {} {}'.format(t, res_num, max_v))
|
|
*출처 : 소프트웨어 엑스퍼트 아카데미 1861번 정사각형 방
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
반응형
'Algorithm > SW Expert Academy' 카테고리의 다른 글
| 0305_SW 2819번 : 숫자 이어 붙이기 (0) | 2020.03.05 |
|---|---|
| 0227_ 오늘도 고생했다 .. SW 1258번 : 행렬찾기 (0) | 2020.02.28 |