문제 링크
https://www.codetree.ai/frequent-problems/hide-and-seek/description
코드트리
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
풀이
고려해야하는 조건들이 매우 많아 까다로웠던 문제이다.
소용돌이로 이동하는 문제는 풀어보았는데, 이동 방향이 틀어지는 지점이라면 방향을 바로 튼다는 점을 어떻게 구현해야할지 몰라,
이동 위치에 다음 이동할 위치의 방향을 기록한다는 아이디어만 참고하여 구현하였다.
구현 방식은 다음과 같다.
next_dir 배열에는 술래가 중앙에서 시작하였을 때, 위치 별 다음 이동할 방향을 기록한다.
next_dir_reverse 배열에는 술래가 (0,0) 위치에서 시작하였을 때, 위치 별 다음 이동할 방향을 기록한다.
소용돌이처럼 이동하면서, 방향을 꺾는 지점에서 방향을 틀고 그 값을 넣어주면 된다.
단, 고려해야할 점은 양 끝에 해당하는 위치(1행 1열) 혹은 정중앙에 도달하게 된다면, 이 경우 역시 방향을 바로 틀어줘야한다.
따라서 next_dir의 (0,0) 위치에는 아래를 바라보는 방향을 넣어줘야하고
next_dir_reverse의 정중앙 위치에는 위를 바라보는 방향을 넣어줘야 한다.
def order_init():
# 방향 인덱스는 위 -> 오른 -> 아래 -> 왼
# next_dir[0][0]= 0
tmp_d = 0
nx = s_x
ny = s_y
for i in range(1,n+1):
if i % 2 :
for j in range(i):
nx += dx[0]
ny += dy[0]
# (0,0) 위치에는 아래를 바라보는 방향 넣어줌
if nx < 0 :
nx -= dx[0]
ny -= dy[0]
next_dir[nx][ny] = 2
return
# 이동 방향을 꺾는 지점마다 방향을 틀고 넣어줌
if j == i-1:
tmp_d = (tmp_d +1)%4
next_dir[nx][ny] = tmp_d
else :
next_dir[nx][ny] = tmp_d
for j in range(i):
nx += dx[1]
ny += dy[1]
# 이동 방향을 꺾는 지점마다 방향을 틀고 넣어줌
if j == i - 1:
tmp_d = (tmp_d + 1) % 4
next_dir[nx][ny] = tmp_d
else:
next_dir[nx][ny] = tmp_d
else :
for j in range(i):
nx += dx[2]
ny += dy[2]
# 이동 방향을 꺾는 지점마다 방향을 틀고 넣어줌
if j == i - 1:
tmp_d = (tmp_d + 1) % 4
next_dir[nx][ny] = tmp_d
else:
next_dir[nx][ny] = tmp_d
for j in range(i):
nx += dx[3]
ny += dy[3]
# 이동 방향을 꺾는 지점마다 방향을 틀고 넣어줌
if j == i - 1:
tmp_d = (tmp_d + 1) % 4
next_dir[nx][ny] = tmp_d
else:
next_dir[nx][ny] = tmp_d아래는 (0,0)에서 이동할 때의 방향 기록이다.
def reverse_order_init():
tmp_d = 2
nx = n-1
ny = 0
# (0,0) 위치에서 아래쪽을 바라보고 시작
next_dir_reverse[0][0] = 2
# 맨 처음 아래쪽으로 이동할 때 방향 기록
for i in range(n-1):
next_dir_reverse[i][0] = tmp_d
tmp_d = (tmp_d-1)%4
next_dir_reverse[n-1][0] = tmp_d
for i in range(n-1, 0, -1):
if i % 2 :
for j in range(i):
nx += dx[3]
ny += dy[3]
# 이동 방향을 틀 때
if j == i-1 :
tmp_d = (tmp_d - 1) % 4
next_dir_reverse[nx][ny] = tmp_d
else:
next_dir_reverse[nx][ny] = tmp_d
for j in range(i):
nx += dx[2]
ny += dy[2]
# 정중앙에서는 위를 바라보는 방향 넣어줌
if nx == n//2 and ny == n//2:
next_dir_reverse[nx][ny] = 0
return
if j == i - 1:
tmp_d = (tmp_d - 1) % 4
next_dir_reverse[nx][ny] = tmp_d
else:
next_dir_reverse[nx][ny] = tmp_d
else:
for j in range(i):
nx += dx[1]
ny += dy[1]
if j == i - 1:
tmp_d = (tmp_d - 1) % 4
next_dir_reverse[nx][ny] = tmp_d
else:
next_dir_reverse[nx][ny] = tmp_d
for j in range(i):
nx += dx[0]
ny += dy[0]
if j == i - 1:
tmp_d = (tmp_d - 1) % 4
next_dir_reverse[nx][ny] = tmp_d
else:
next_dir_reverse[nx][ny] = tmp_d
1. 도망자가 이동한다.
도망자는 동시에 이동하므로, tmp 라는 배열에 저장한다.
여기서도 고려해야할 점이 많은데,
1) 술래와 거리가 3보다 크다면 원래 자리에 기록한다.
2) 해당 위치의 도망자별로 방향에 맞게 이동한다.
- 범위를 벗어난다면 방향을 틀고, 그 방향으로 이동한다. 만약 그 자리에 술래가 있다면 원래 자리에 바뀐 방향만 기록하고, 술래가 없다면 이동한 위치에 방향을 기록한다.
- 범위가 벗어나지 않는다면, 이동 위치에 술래가 있다면 원래 자리에 그대로 기록하고, 없다면 이동한 위치에 방향을 기록한다.
3) graph 를 갱신한다.
def run():
global graph
tmp = [[ [] for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if len(graph[i][j]) == 0 :
continue
# 술래와 거리 3보다 큼
if abs(i-s_x) + abs(j-s_y) > 3 :
tmp[i][j].extend(graph[i][j])
continue
for d in graph[i][j]:
nx = i + dx[d]
ny = j + dy[d]
# 범위를 벗어남
if nx <0 or nx >= n or ny < 0 or ny >= n:
# 방향 전환
d = (d+2) % 4
nx = i + dx[d]
ny = j + dy[d]
# 이동한 위치에 술래가 없으면 이동
if not (nx==s_x and ny==s_y):
tmp[nx][ny].append(d)
# 술래가 있다면 원래 자리에 바뀐 방향 기록
else :
tmp[i][j].append(d)
else :
# 술래가 있다면 이동 안함
if nx == s_x and ny == s_y :
tmp[i][j].append(d)
# 술래가 없다면 이동
else :
tmp[nx][ny].append(d)
graph = tmp2. 술래가 이동하여 도망자를 잡는다.
1) forward라는 변수를 통해 현재 이동 방향이 중앙에서 시작한건지, 1행 1열에서 시작한건지 체크한다.
따라서, 현재 위치에서 다음으로 이동할 방향에 맞게 이동한다.
( 여기서 forward에 따라 다르게 처리해주지 못해서 테스트 케이스 6번이 통과하지 못했다ㅠㅠ 디버깅 엄청 함)
2) 현재 위치포함 다음 이동 방향에 맞게 3칸을 확인한다.
여기서 주의할 점은 현재 위치 포함 3칸이라는 것.. 그리고 현재 위치에도 나무가 있으면 도망자를 잡지 못한다.
- 만약 나무가 없고, 도망자가 있다면 도망자의 수를 더하고 현재 위치의 도망자를 제거한다.
3) 현재 턴 * 잡은 도망자 수를 갱신한다.
4) 만약 현재 방향이 정방향(중앙에서 시작)이고 (0,0)이라면 forward 변수를 false 로 바꾼다. (방향 전환)
만약 현재 방향이 역방향(1행 1열에서 시작)이고, 정중앙이라면 forward 변수를 true로 바꾼다.
def s_move():
global s_x, s_y, turn, ans, forward
# 현재 위치에서 이동할 방향
if forward:
s_d = next_dir[s_x][s_y]
else :
s_d = next_dir_reverse[s_x][s_y]
# 이동
if forward :
s_x += dx[s_d]
s_y += dy[s_d]
# 탐색할 방향 저장
s_d = next_dir[s_x][s_y]
else :
s_x += dx[s_d]
s_y += dy[s_d]
s_d = next_dir_reverse[s_x][s_y]
cnt = 0
# 도망자 잡기
for i in range(0,3):
nx = s_x + dx[s_d] * i
ny = s_y + dy[s_d] * i
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if not tree[nx][ny] :
if len(graph[nx][ny]) > 0 :
cnt += len(graph[nx][ny])
graph[nx][ny] = []
ans += (cnt * turn)
# 방향 전환 체크
if forward and s_x == 0 and s_y == 0 :
forward = False
if not forward and s_x == n//2 and s_y == n//2 :
forward = True전체 코드는 아래와 같다.
def s_move():
global s_x, s_y, turn, ans, forward
# 현재 위치에서 이동할 방향
if forward:
s_d = next_dir[s_x][s_y]
else :
s_d = next_dir_reverse[s_x][s_y]
# 이동
if forward :
s_x += dx[s_d]
s_y += dy[s_d]
# 탐색할 방향 저장
s_d = next_dir[s_x][s_y]
else :
s_x += dx[s_d]
s_y += dy[s_d]
s_d = next_dir_reverse[s_x][s_y]
cnt = 0
# 도망자 잡기
for i in range(0,3):
nx = s_x + dx[s_d] * i
ny = s_y + dy[s_d] * i
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if not tree[nx][ny] :
if len(graph[nx][ny]) > 0 :
cnt += len(graph[nx][ny])
graph[nx][ny] = []
ans += (cnt * turn)
# 방향 전환 체크
if forward and s_x == 0 and s_y == 0 :
forward = False
if not forward and s_x == n//2 and s_y == n//2 :
forward = True
def order_init():
# 방향 인덱스는 위 -> 오른 -> 아래 -> 왼
# next_dir[0][0]= 0
tmp_d = 0
nx = s_x
ny = s_y
for i in range(1,n+1):
if i % 2 :
for j in range(i):
nx += dx[0]
ny += dy[0]
# (0,0) 위치에는 아래를 바라보는 방향 넣어줌
if nx < 0 :
nx -= dx[0]
ny -= dy[0]
next_dir[nx][ny] = 2
return
# 이동 방향을 꺾는 지점마다 방향을 틀고 넣어줌
if j == i-1:
tmp_d = (tmp_d +1)%4
next_dir[nx][ny] = tmp_d
else :
next_dir[nx][ny] = tmp_d
for j in range(i):
nx += dx[1]
ny += dy[1]
# 이동 방향을 꺾는 지점마다 방향을 틀고 넣어줌
if j == i - 1:
tmp_d = (tmp_d + 1) % 4
next_dir[nx][ny] = tmp_d
else:
next_dir[nx][ny] = tmp_d
else :
for j in range(i):
nx += dx[2]
ny += dy[2]
# 이동 방향을 꺾는 지점마다 방향을 틀고 넣어줌
if j == i - 1:
tmp_d = (tmp_d + 1) % 4
next_dir[nx][ny] = tmp_d
else:
next_dir[nx][ny] = tmp_d
for j in range(i):
nx += dx[3]
ny += dy[3]
# 이동 방향을 꺾는 지점마다 방향을 틀고 넣어줌
if j == i - 1:
tmp_d = (tmp_d + 1) % 4
next_dir[nx][ny] = tmp_d
else:
next_dir[nx][ny] = tmp_d
def reverse_order_init():
tmp_d = 2
nx = n-1
ny = 0
# (0,0) 위치에서 아래쪽을 바라보고 시작
next_dir_reverse[0][0] = 2
# 맨 처음 아래쪽으로 이동할 때 방향 기록
for i in range(n-1):
next_dir_reverse[i][0] = tmp_d
tmp_d = (tmp_d-1)%4
next_dir_reverse[n-1][0] = tmp_d
for i in range(n-1, 0, -1):
if i % 2 :
for j in range(i):
nx += dx[3]
ny += dy[3]
# 이동 방향을 틀 때
if j == i-1 :
tmp_d = (tmp_d - 1) % 4
next_dir_reverse[nx][ny] = tmp_d
else:
next_dir_reverse[nx][ny] = tmp_d
for j in range(i):
nx += dx[2]
ny += dy[2]
# 정중앙에서는 위를 바라보는 방향 넣어줌
if nx == n//2 and ny == n//2:
next_dir_reverse[nx][ny] = 0
return
if j == i - 1:
tmp_d = (tmp_d - 1) % 4
next_dir_reverse[nx][ny] = tmp_d
else:
next_dir_reverse[nx][ny] = tmp_d
else:
for j in range(i):
nx += dx[1]
ny += dy[1]
if j == i - 1:
tmp_d = (tmp_d - 1) % 4
next_dir_reverse[nx][ny] = tmp_d
else:
next_dir_reverse[nx][ny] = tmp_d
for j in range(i):
nx += dx[0]
ny += dy[0]
if j == i - 1:
tmp_d = (tmp_d - 1) % 4
next_dir_reverse[nx][ny] = tmp_d
else:
next_dir_reverse[nx][ny] = tmp_d
def run():
global graph
tmp = [[ [] for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if len(graph[i][j]) == 0 :
continue
# 술래와 거리 3보다 큼
if abs(i-s_x) + abs(j-s_y) > 3 :
tmp[i][j].extend(graph[i][j])
continue
for d in graph[i][j]:
nx = i + dx[d]
ny = j + dy[d]
# 범위를 벗어남
if nx <0 or nx >= n or ny < 0 or ny >= n:
# 방향 전환
d = (d+2) % 4
nx = i + dx[d]
ny = j + dy[d]
# 이동한 위치에 술래가 없으면 이동
if not (nx==s_x and ny==s_y):
tmp[nx][ny].append(d)
# 술래가 있다면 원래 자리에 바뀐 방향 기록
else :
tmp[i][j].append(d)
else :
# 술래가 있다면 이동 안함
if nx == s_x and ny == s_y :
tmp[i][j].append(d)
# 술래가 없다면 이동
else :
tmp[nx][ny].append(d)
graph = tmp
n, m , h , k = map(int,input().split())
order = []
graph = [ [[] for _ in range(n)] for _ in range(n)]
tree = [ [0] * n for _ in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
next_dir = [ [0] * n for _ in range(n)]
next_dir_reverse = [ [0] *n for _ in range(n)]
forward = True
for _ in range(m):
a, b, d = map(int,input().split())
if d == 1:
# 오른쪽 보고 시작
graph[a-1][b-1].append(1)
else:
# 아래쪽 보고 시작
graph[a-1][b-1].append(2)
for _ in range(h):
x, y = map(int,input().split())
tree[x-1][y-1] = 1
s_x = n//2
s_y = n//2
turn = 1
ans = 0
# 해당 위치에서 탐색할 방향 저장
order_init()
reverse_order_init()
for _ in range(k):
run()
s_move()
turn += 1
print(ans)'개발 > algorithm' 카테고리의 다른 글
| [백준 15685번] 드래곤 커브 - python (0) | 2022.10.13 |
|---|---|
| [백준 12100번] 2048 (Easy) - python (0) | 2022.10.13 |
| [백준 23289번] 온풍기 안녕! - Python (0) | 2022.10.12 |
| [백준 21610번] 마법사 상어와 비바라기 - Python (0) | 2022.10.11 |
| [백준 17837번] 새로운 게임 2 - python (1) | 2022.10.08 |