'''
sudo
gravity: 쭉 내린다
더이상 못내리면 move = False
cr,cc,d 는 어떻게 관리? -> 전역변수?
for c,d in golems:
cr,cc = 1,c
idx = 1
ncr, ncc, nd = cr, cc, d
while True:
grav = gravity()
lr = left_rotate()
rr = right_rotate()
if grav== False and lr == False and rr == False:
break
check = [[ncr+1,cc],[ncr,cc-1],[ncr,cc],[ncr,cc+1],[ncr-1,ncc]]
idx += 1
'''
수정 후 코드
from collections import deque
R, C, K = map(int, input().rstrip().split())
maps = [[0] * (C + 1) for _ in range(R + 3)]
direct = ((-1, 0), (0, 1), (1, 0), (0, -1))
golem_point = {} # 각 idx를 가진 골렘의 위치, 출구 방향 좌표
# c 골렘이 출발하는 열
for i in range(3, R + 3):
maps[i][-1] = -1
# 골렘 정보
golem = [list(map(int, input().split())) for _ in range(K)]
row_score = 0 # 각 행에 속한 정령의 수
def left_rotate(idx):
global golem_point
# 왼쪽 확인
cr, cc, d = golem_point[idx]
check = [[cr - 1, cc - 1], [cr, cc - 2], [cr + 1, cc - 1], [cr + 1, cc - 2], [cr + 2, cc - 1]]
for row, col in check:
if 0 <= row < R + 3 and 0 <= col < C + 1 and maps[row][col] == 0:
continue
else:
return False
golem_point[idx][2] = (d - 1) % 4
golem_point[idx][0], golem_point[idx][1] = cr + 1, cc - 1
return True
def right_rotate(idx):
global golem_point
cr, cc, d = golem_point[idx]
check = [[cr - 1, cc + 1], [cr, cc + 2], [cr + 1, cc + 1], [cr + 2, cc + 1], [cr + 1, cc + 2]]
for row, col in check:
if 0 <= row < R + 3 and 0 <= col < C + 1 and maps[row][col] == 0:
continue
else:
return False
golem_point[idx][2] = (d + 1) % 4
golem_point[idx][0], golem_point[idx][1] = cr + 1, cc + 1
return True
def exit_man(cr, cc, idx):
queue = deque([[cr, cc, idx]])
MAX_row = float('-inf')
visited = [[False] * (C + 1) for _ in range(R + 3)]
visited[cr][cc] = True
while queue:
q = queue.popleft()
qx, qy, qidx = q[0], q[1], q[2]
d = golem_point[qidx][2] # 출구 정보
dx, dy = golem_point[qidx][0] + direct[d][0], golem_point[qidx][1] + direct[d][1]
for i in range(4):
nx = qx + direct[i][0]
ny = qy + direct[i][1]
if 2 <= nx < R + 3 and 0 <= ny < C and maps[nx][ny] > 0 and visited[nx][ny] == False:
if (qx == dx and qy == dy) or maps[nx][ny] == qidx:
# queue에 넣는다 => 다음에 갈 수 있다
queue.append([nx, ny, maps[nx][ny]])
visited[nx][ny] = True
if nx > MAX_row:
MAX_row = nx
if MAX_row == R + 2:
return MAX_row
return MAX_row
def gravity(idx):
global golem_point
cr, cc, d = golem_point[idx]
ncr = cr + 1
while True:
if ncr + 1 < len(maps) and maps[ncr][cc - 1] == 0 and maps[ncr][cc + 1] == 0 and maps[ncr + 1][cc] == 0:
ncr += 1
else:
ncr -= 1
break
if ncr > cr:
golem_point[idx] = [ncr, cc, d]
return True
else:
return False
for g in range(len(golem)):
# g = c, d #열과 출구 방향
c, d = golem[g]
# 골렘 정보를 바탕으로 좌표 세팅
# 골렘 초기 위치 정보 저장
c = c - 1
cr, cc = 1, c
idx = g + 1
golem_point[idx] = [cr, cc, d]
# golem_set(c, idx)
while True:
move1 = gravity(idx)
move2 = left_rotate(idx)
move3 = right_rotate(idx)
if move1 == False and move2 == False and move3 == False:
break
ncx, ncy, d = golem_point[idx]
check = [[ncx - 1, ncy], [ncx, ncy - 1], [ncx, ncy], [ncx, ncy + 1], [ncx + 1, ncy]]
for nx, ny in check:
maps[nx][ny] = idx
new_maps = False
for nx, ny in check:
if nx < 3:
maps = [[0] * (C + 1) for _ in range(R + 3)]
# c 골렘이 출발하는 열
for i in range(2, R + 3):
maps[i][-1] = -1
new_maps = True
if new_maps == True:
continue
if nx > 3:
MAX_row = exit_man(ncx, ncy, idx)
if MAX_row > 0:
row_score += MAX_row - 2
print(row_score)
수정 전에는 exit_man (bfs) 부분이 조건문이 이상했음.
큐에 넣고 방문처리를 해줘야하는데,
방문만 하면 무조건 True를 갈겨버려서
틀렷음..
수정된 부분
def exit_man(cr, cc, idx):
queue = deque([[cr, cc, idx]])
MAX_row = float('-inf')
visited = [[False] * (C + 1) for _ in range(R + 3)]
visited[cr][cc] = True
while queue:
q = queue.popleft()
qx, qy, qidx = q[0], q[1], q[2]
d = golem_point[qidx][2] # 출구 정보
dx, dy = golem_point[qidx][0] + direct[d][0], golem_point[qidx][1] + direct[d][1]
for i in range(4):
nx = qx + direct[i][0]
ny = qy + direct[i][1]
if 2 <= nx < R + 3 and 0 <= ny < C and maps[nx][ny] > 0 and visited[nx][ny] == False:
if (qx == dx and qy == dy) or maps[nx][ny] == qidx:
# queue에 넣는다 => 다음에 갈 수 있다
queue.append([nx, ny, maps[nx][ny]])
visited[nx][ny] = True
if nx > MAX_row:
MAX_row = nx
if MAX_row == R + 2:
return MAX_row
return MAX_row
수정 전 코드
def exit_man(cr, cc, idx):
queue = deque([[cr, cc, idx]])
MAX_row = float('-inf')
visited = [[False] * (C + 1) for _ in range(R + 3)]
while queue:
q = queue.popleft()
qx, qy, qidx = q[0], q[1], q[2]
d = golem_point[qidx][2] # 출구 정보
dx, dy = golem_point[qidx][0] + direct[d][0], golem_point[qidx][1] + direct[d][1]
for i in range(4):
nx = qx + direct[i][0]
ny = qy + direct[i][1]
if 2 <= nx < R + 3 and 0 <= ny < C and maps[nx][ny] > 0 and visited[nx][ny] == False:
visited[nx][ny] = True # 문제의 부분 두둥탁
if nx > MAX_row:
MAX_row = nx
if MAX_row == R + 2:
return MAX_row
if (nx == dx and ny == dy) or (qx == dx and qy == dy) or maps[nx][ny] == qidx:
queue.append([nx, ny, maps[nx][ny]])
return MAX_row
from collections import deque
R, C, K = map(int, input().rstrip().split())
maps = [[0] * (C + 1) for _ in range(R + 3)]
direct = ((-1, 0), (0, 1), (1, 0), (0, -1)) # 북동남서
# c 골렘이 출발하는 열
for i in range(3, R + 3):
maps[i][-1] = -1
# 골렘 정보
golem = [list(map(int, input().split())) for _ in range(K)]
# 골렘의 초기 c열과, 방향이 주어짐
golem_point = {i+1:[1,golem[i][0]-1,golem[i][1]] for i in range(len(golem))} # 처음에는 1행에서 시작
exit_map = [[False]*(C+1) for _ in range(R+3)]
answer = 0
def bfs(idx):
# 탈출구 방향 유의
cx,cy,_ = golem_point[idx]
queue = deque([[cx,cy]])
visited = [[False] * (C+1) for _ in range(R+3)]
visited[cx][cy] = True
MAX = 0
while queue:
q = queue.popleft()
qx,qy = q[0], q[1]
if qx == len(maps):
return qx - 2
if MAX < qx:
MAX = qx
c_idx = maps[qx][qy] # 현재 위치의 인덱스
d = golem_point[c_idx][2]
# ex, ey = golem_point[c_idx][0] + direct[d][0], golem_point[c_idx][1] + direct[d][1]
for i in range(4):
x = qx + direct[i][0]
y = qy + direct[i][1]
if 0 <= x < R+3 and 0 <= y < C and visited[x][y] == False and maps[x][y] > 0:
# 이동한 위치가 해당 골렘의 영역이거나
# 현재 위치가 해당 골렘의 출구라면
if maps[x][y] == c_idx or exit_map[qx][qy] == True:
queue.append([x,y])
visited[x][y] = True
return MAX - 2
def gravity(idx):
# 가장 남쪽으로 내려가본다.
cx,cy,d = golem_point[idx]
ncx = cx
while True:
if ncx +1< len(maps) and maps[ncx+1][cy] == 0 and maps[ncx][cy+1] == 0 and maps[ncx][cy-1] == 0:
ncx += 1
else:
ncx -= 1
break
if ncx > cx:
golem_point[idx] = [ncx,cy,d]
return True
else:
return False
# rotate 시 출구 방향도 함꼐 rotate 됨
def left_rotate(idx):
global golem_point
cx,cy,d= golem_point[idx]
gm = [[cx,cy-2],[cx-1,cy-1],[cx+1,cy-1],[cx+1,cy-2],[cx+2,cy-1]]
for x,y in gm:
if 0<= x < R+3 and 0 <= y < C and maps[x][y] == 0:
continue
else:
return False
nd = (d-1) % 4
golem_point[idx] = [cx+1,cy-1,nd]
return True
def right_rotate(idx):
global golem_point
cx,cy,d= golem_point[idx]
gm = [[cx,cy+2],[cx-1,cy+1],[cx+1,cy+1],[cx+1,cy+2],[cx+2,cy+1]]
for x,y in gm:
if 0<= x < R+3 and 0 <= y < C and maps[x][y] == 0:
continue
else:
return False
nd = (d+1) % 4
golem_point[idx] = [cx+1,cy+1,nd]
return True
for idx in golem_point:
while True:
# [1] 남쪽으로 내려간다
move1 = gravity(idx)
# [2] 남쪽으로 못내려가면 서쪽 방향으로 회전한다.
move2 = left_rotate(idx)
# # [3] 서쪽으로도 못내려가면 동쪽으로 회전한다.
move3 = right_rotate(idx)
# [4] 더이상 내려갈 방향이 없으면 탈출한다.
if move1 == False and move2 == False and move3 == False:
break
# 골렘 최종 좌표 표시
cx,cy,d = golem_point[idx]
# [4-0] 만약 골렘의 몸 일부가 숲을 벗어나지 않았다면 좌표 표시
new_ = False
if 4 > cx :
new_ = True
if new_ == False:
for x, y in [[cx, cy], [cx + 1, cy], [cx - 1, cy], [cx, cy + 1], [cx, cy - 1]]:
maps[x][y] = idx
ex,ey = cx + direct[d][0],cy + direct[d][1]
exit_map[ex][ey] = True
# [4-0-1] 탈출했을때 탈출구가 이어지면 옆 골렘으로 이동 가능
score = bfs(idx)
# [4-0-2] 가장 밑으로 내려왔을때 행의 높이를 적는다.
answer += score
# [4-1] 골렘의 몸 일부가 숲을 벗어났다면, 해당 골렘은 죽이고(점수X) 새로운 맵
else:
maps = [[0] * (C + 1) for _ in range(R + 3)]
exit_map = [[False] * (C + 1) for _ in range(R + 3)]
# for i in maps:
# print(i)
# print()
print(answer)
수정 전 코드와 수정 후 코드의 차이 분석
1. 수정 전 코드:
visited[nx][ny] = True 부분이 queue.append와 상관없이 바로 실행된다. 즉, 이동 가능한지 확인하기 전에 해당 좌표를 방문 처리하고 있다.
조건절에서 (nx == dx and ny == dy), (qx == dx and qy == dy), maps[nx][ny] == qidx 세 가지 경우 중 하나가 성립하면 큐에 새로운 좌표를 추가한다.
2. 수정 후 코드:
visited[cr][cc] = True로 시작 좌표를 먼저 방문 처리하여 중복 방문을 방지한다.
큐에 좌표를 추가하는 부분을 조건문 (qx == dx and qy == dy) 또는 maps[nx][ny] == qidx에 의해서만 실행되도록 변경했다.
큐에 좌표를 추가한 후에 visited[nx][ny] = True를 설정하여, 실제로 큐에 추가된 좌표만 방문 처리한다. 이를 통해 불필요한 방문 처리를 방지하고, 잘못된 경로 탐색을 막는다.
조건 해결 방법
수정 후에는 이동 가능한지 확인한 후에만 큐에 추가하고 방문 처리를 하므로, 중복 방문과 불필요한 경로 탐색을 막아준다. visited를 큐에 넣기 전에 설정하지 않고, 큐에 추가된 좌표만 방문 처리하는 방식으로 바꿔야 조건에 맞는 좌표 탐색을 효율적으로 수행할 수 있다.
from collections import deque
R, C, K = map(int, input().rstrip().split())
maps = [[0] * (C + 1) for _ in range(R + 3)]
direct = ((-1, 0), (0, 1), (1, 0), (0, -1))
golem_point = {} # 각 idx를 가진 골렘의 위치, 출구 방향 좌표
# c 골렘이 출발하는 열
for i in range(3, R + 3):
maps[i][-1] = -1
# 골렘 정보
golem = [list(map(int, input().split())) for _ in range(K)]
row_score = 0 # 각 행에 속한 정령의 수
def left_rotate(idx):
global golem_point
# 왼쪽 확인
cr, cc, d = golem_point[idx]
check = [[cr - 1, cc - 1], [cr, cc - 2], [cr + 1, cc - 1], [cr + 1, cc - 2], [cr + 2, cc - 1]]
for row, col in check:
if 0 <= row < R + 3 and 0 <= col < C + 1 and maps[row][col] == 0:
continue
else:
return False
golem_point[idx][2] = (d - 1) % 4
golem_point[idx][0], golem_point[idx][1] = cr + 1, cc - 1
return True
def right_rotate(idx):
global golem_point
cr, cc, d = golem_point[idx]
check = [[cr - 1, cc + 1], [cr, cc + 2], [cr + 1, cc + 1], [cr + 2, cc + 1], [cr + 1, cc + 2]]
for row, col in check:
if 0 <= row < R + 3 and 0 <= col < C + 1 and maps[row][col] == 0:
continue
else:
return False
golem_point[idx][2] = (d + 1) % 4
golem_point[idx][0], golem_point[idx][1] = cr + 1, cc + 1
return True
def exit_man(cr, cc, idx):
queue = deque([[cr, cc, idx]])
MAX_row = float('-inf')
visited = [[False] * (C + 1) for _ in range(R + 3)]
while queue:
q = queue.popleft()
qx, qy, qidx = q[0], q[1], q[2]
d = golem_point[qidx][2] # 출구 정보
dx, dy = golem_point[qidx][0] + direct[d][0], golem_point[qidx][1] + direct[d][1]
for i in range(4):
nx = qx + direct[i][0]
ny = qy + direct[i][1]
if 2 <= nx < R + 3 and 0 <= ny < C and maps[nx][ny] > 0 and visited[nx][ny] == False:
visited[nx][ny] = True
if nx > MAX_row:
MAX_row = nx
if MAX_row == R + 2:
return MAX_row
if (nx == dx and ny == dy) or (qx == dx and qy == dy) or maps[nx][ny] == qidx:
queue.append([nx, ny, maps[nx][ny]])
return MAX_row
def gravity(idx):
global golem_point
cr, cc, d = golem_point[idx]
ncr = cr + 1
while True:
if ncr + 1 < len(maps) and maps[ncr][cc - 1] == 0 and maps[ncr][cc + 1] == 0 and maps[ncr + 1][cc] == 0:
ncr += 1
else:
ncr -= 1
break
if ncr > cr:
golem_point[idx] = [ncr, cc, d]
return True
else:
return False
def golem_set(c, idx):
global maps
golem_body = ((0, c), (1, c - 1), (1, c), (1, c + 1), (2, c))
new_maps = False
for x, y in golem_body:
if maps[x][y] != 0:
new_maps = True
break
if new_maps:
maps = [[0] * (C + 1) for _ in range(R + 3)]
# c 골렘이 출발하는 열
for i in range(2, R + 3):
maps[i][-1] = -1
for g in range(len(golem)):
# g = c, d #열과 출구 방향
c, d = golem[g]
# 골렘 정보를 바탕으로 좌표 세팅
# 골렘 초기 위치 정보 저장
c = c - 1
cr, cc = 1, c
idx = g + 1
golem_point[idx] = [cr, cc, d]
golem_set(c, idx)
while True:
move1 = gravity(idx)
move2 = left_rotate(idx)
move3 = right_rotate(idx)
if move1 == False and move2 == False and move3 == False:
break
ncx, ncy, d = golem_point[idx]
check = [[ncx - 1, ncy], [ncx, ncy - 1], [ncx, ncy], [ncx, ncy + 1], [ncx + 1, ncy]]
for nx, ny in check:
maps[nx][ny] = idx
if nx > 3:
MAX_row = exit_man(ncx, ncy, idx)
if MAX_row > 0:
row_score += MAX_row - 2
# for i in maps:
# print(i)
# print()
print(row_score)
1번 테케 통과
2번 테케 X
7 9 6
4 1
5 1
2 1
8 1
2 2
6 0
※ 알아야 할 것
- 수정 전 코드는 방문 여부를 큐에 추가하기 전에 설정하여 불필요한 경로 탐색이 발생했다.
