BAEKJOON 12100
문제
입력
—–
나의 처음 코드
어제 포스팅한 구슬넣기 문제랑 비슷하다. 전체를 한번에 이동하는 것. 여기 문제에서는 배열전체를 계속해서 shallow copy로 저장해서, 매개변수로 넣어주던가(dfs) 아니면 큐에 넣어준다(bfs). 사실 bfs로 풀려고 했지만, 최대 크기 20x20를 배열에 계속 때려박는다고 생각하니 뭔가 무서워서 안했다,,, 헤헤,,, 사실 이거 디테일한 조건들을 고려 안하면서 짜가지고 시간을 엄청 낭비한 문제이다. 블록이 겹쳤을 때 처리하는 것, 이미 합친 블록을 처리하는 방법, 안 합치면 그전 좌표로 가는 것 등등. 진짜 다음에는 노트에 조건들을 다 써놓고 해야겠다. 코드는 다음과 같다.
#규칙에 조건을 두는 것에 세세한 정확성이 필요할듯
#조그만 한 곳에 예외로 자꾸 틀린다.
#문제를 꼼꼼히 읽어볼 것
N = int(input())
map_list = []
block_max = -1 #최대값
for i in range(N):
map_list.append(list(map(int, input().split())))
#어떻게 이동해도 안될 때, 기본에 가진 원소중에 max가 최대값
block_max = max(block_max, max(map_list[i]))
ud_list = [-1, 1, 0, 0]
rl_list = [0, 0, 1, -1]
def move(loc_map, now_coord, way):
global block_max
#합쳐진 블록들을 표시하고, 다시 또 합치는 일 없게
check_list = [0] * N
#배열 shallow copy부분
local_map = [[] for _ in range(N)]
for i in range(N):
local_map[i] = loc_map[i].copy()
#위쪽, 아래쪽으로 기울때
if way == 0 or way == 1:
col = now_coord[1]
for raw in range(N):
if way == 1:
raw = N - 1 - raw
now_num = local_map[raw][col]
#지금 숫자가 0일 때는 pass
if now_num == 0:
continue
tmp_raw, tmp_col = raw, now_coord[1]
tmp_raw += ud_list[way]
tmp_col += rl_list[way]
#0이 아닌 다른 숫자 만나기 전까지 진행
while tmp_raw >= 0 and tmp_col >= 0 and tmp_raw < N and tmp_col < N and local_map[tmp_raw][tmp_col] == 0:
tmp_raw += ud_list[way]
tmp_col += rl_list[way]
#while문에 나왔을 때 index 초과이면
if tmp_raw < 0 or tmp_raw >= N:
tmp_raw -= ud_list[way]
#움직이 있었을 때
if tmp_raw != raw:
#지금 도착한 좌표랑 숫자가 같을 때
if check_list[tmp_raw] != 1 and now_num == local_map[tmp_raw][tmp_col]:
check_list[tmp_raw] = 1
local_map[raw][col] = 0
local_map[tmp_raw][tmp_col] = local_map[tmp_raw][tmp_col] *2
#지금 도착한 좌표랑 숫자가 같지 않을 때
else:
#지금 좌표가 0이 아니면, 그 전좌표로.
if local_map[tmp_raw][tmp_col] != 0:
tmp_raw -= ud_list[way]
tmp_col -= rl_list[way]
#움직였는데 처음 좌표랑 다를 때
if tmp_raw != raw:
moved = True
local_map[raw][col] = 0
local_map[tmp_raw][tmp_col] = now_num
#위의 주석이랑 동일
elif way == 2 or way == 3:
raw = now_coord[0]
for col in range(N):
if way == 2:
col = N - 1 - col
now_num = local_map[raw][col]
#지금 숫자가 0일 때는 pass
if now_num == 0:
continue
tmp_raw, tmp_col = now_coord[0], col
tmp_raw += ud_list[way]
tmp_col += rl_list[way]
#0이 아닌 다른 숫자 만나기 전까지 진행
while tmp_raw >= 0 and tmp_col >= 0 and tmp_raw < N and tmp_col < N and local_map[tmp_raw][tmp_col] == 0:
tmp_raw += ud_list[way]
tmp_col += rl_list[way]
#while문에 나왔을 때 index 초과이면
if tmp_col < 0 or tmp_col >= N:
tmp_col -= rl_list[way]
#움직이 있었을 때
if tmp_col != col:
#지금 도착한 좌표랑 숫자가 같을 때
if check_list[tmp_col] != 1 and now_num == local_map[tmp_raw][tmp_col]:
check_list[tmp_col] = 1
local_map[raw][col] = 0
local_map[tmp_raw][tmp_col] = local_map[tmp_raw][tmp_col] *2
moved = True
#지금 도착한 좌표랑 숫자가 같지 않을 때
else:
if local_map[tmp_raw][tmp_col] != 0:
tmp_raw -= ud_list[way]
tmp_col -= rl_list[way]
if tmp_col != col:
moved = True
local_map[raw][col] = 0
local_map[tmp_raw][tmp_col] = now_num
return local_map, moved
def solution(map_list, count):
global N
global block_max
if count == 5:
for i in map_list:
block_max = max(block_max, max(i))
return
#위쏠, 아쏠, 오쏠, 왼쏠
tmp_list = [[] for _ in range(N)]
for i in range(N):
tmp_list[i] = map_list[i].copy()
for way in range(4):
moved = False
if way == 0:
for idx in range(N):
if idx == 0:
local_map, tmp_moved = move(tmp_list, (0, idx), way)
else:
local_map, tmp_moved = move(local_map, (0, idx), way)
elif way == 1:
for idx in range(N):
if idx == 0:
local_map, tmp_moved = move(tmp_list, (N-1, idx), way)
else:
local_map, tmp_moved = move(local_map, (N-1, idx), way)
elif way == 2:
for idx in range(N):
if idx == 0:
local_map, tmp_moved = move(tmp_list, (idx, N-1), way)
else:
local_map, tmp_moved = move(local_map, (idx, N-1), way)
else:
for idx in range(N):
if idx == 0:
local_map, tmp_moved = move(tmp_list, (idx, 0), way)
else:
local_map, tmp_moved = move(local_map, (idx, 0), way)
solution(local_map, count + 1)
solution(map_list, 0)
print(block_max)
mutable, immutable에 대해서 다시 한번 고려해본 문제였다. 왜냐면 copy만 쓰면 다 shallow copy될 줄 알았는데, 배열 안의 배열은 deep copy가 되는 것이었다. 따라서 다음과 같이 해주면 2차배열 shallow copy를 쉽게 할 수 있다.
#not import copy and execute deep copy
tmp_list = [[] for _ in range(N)]
for i in range(N):
tmp_list[i] = map_list[i].copy()
tmp_list[0][0] = 100
print(tmp_list)
print(map_list)
다음 시뮬레이션은 bfs로 한번 풀어봐야겠다.