SWEA_1861_정사각형 방
아이디어 1
-
각 칸에서 재귀함수 사용해 이동한 칸 수 세기
-
N이 최대 1000, N x N인 경우 최대 1000000칸 이동 가능
-
가능한 재귀호출 회수
- python3 대략 1000
- pypy3.6 대략 2300
-
재귀함수 사용 불가!
-
다른 방법을 사용해야겠다.
-
-
반복을 이용한 탐색을 진행해야겠네
-
각 자리에서 탐색을 진행
-
가지치기
-
탐색했던 기록을 저장하여 시작점이 탐색한 적이 있었다면 탐색을 진행하지 않는 것으로 해도 되지 않을까?
-
탐색했던 기록이 그 지점을 시작으로 하는 "경로의 길이"라면, 탐색 중에 해당 지점을 도착하더라도 탐색을 중복하여 할 필요가 없지 않을까?
(이 방법은 쉽지 않았다.)
-
-
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
def search(r, c, count):
stack = [(r, c, count)]
while stack:
cr, cc, c_count = stack.pop()
for di in range(4):
nr = cr + dr[di]
nc = cc + dc[di]
if 0 <= nr < N and 0 <= nc < N:
if BOARD[nr][nc] == BOARD[cr][cc] + 1:
stack.append((nr, nc, c_count + 1))
# 모든 수는 서로 다르기 때문에, 갈 수 있는 방향도 한 곳 밖에는 없다.
break
# 모든 방향을 탐색했지만 갈 수 있는 곳이 없었다.
else:
if c_count != 1:
start_memory[BOARD[r][c]] = c_count
T = int(input())
for tc in range(1, T + 1):
# N: 배열의 크기
N = int(input())
# 탐색할 배열
BOARD = [list(map(int, input().split())) for _ in range(N)]
# 탐색했던 칸을 저장하는 배열
# 이 칸으로 부터
start_memory = [0] * (N * N)
for i in range(N):
for j in range(N):
search(i, j, 1)
# 저장한 배열 중 가장 큰 값을 갖고 있는 가장 작은 인덱스를 찾는다.
max_length = max(start_memory)
result = start_memory.index(max_length)
print(f"#{tc} {result} {max_length}")
아이디어 2
-
N * N까지의 인덱스를 가진 1차원 배열을 만들어 0으로 초기화한다.
-
모든 칸을 순회한다
- 주위를 탐색하여, 나보다 1 큰 값을 가진 칸이 있으면 그 칸의 값을 인덱스로 하는 배열의 칸을 1로 저장한다.
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
def search(sr, sc):
for di in range(4):
nr = sr + dr[di]
nc = sc + dc[di]
if 0 <= nr < N and 0 <= nc < N:
if BOARD[sr][sc] + 1 == BOARD[nr][nc]:
can_progress[BOARD[sr][sc]] = True
break
T = int(input())
for tc in range(1, T + 1):
N = int(input())
BOARD = [list(map(int, input().split())) for _ in range(N)]
# 숫자는 1부터 시작한다.
# 마지막 숫자는 자기보다 큰 숫자가 없기 때문에 사실 1을 더해주지 않아도 된다.
# can_progress = [False] * ((N * N) + 1)
can_progress = [False] * (N * N)
for i in range(N):
for j in range(N):
search(i, j)
# print(can_progress)
# can_progress를 역순으로 탐색하여, 숫자를 셉니다.
max_number = N * N
max_length = 0
count = 1
for i in range((N * N) - 1, 0, -1):
if can_progress[i]:
count += 1
if not can_progress[i - 1]:
if max_length <= count:
max_length = max(max_length, count)
max_number = i
count = 1
print(f"#{tc}", max_number, max_length)
Author And Source
이 문제에 관하여(SWEA_1861_정사각형 방), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@byunghun-jake/SWEA1861정사각형-방저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)