술래잡기(2022 상반기 오전 1번)

문제 링크: https://www.codetree.ai/frequent-problems/hide-and-seek/description

코드트리

2시간 넘게 맞왜틀 시전하다가(토론장에 있던 모든 예제도 다 통과) 이상한 부분 하나와 잘못한 부분 하나를 고치니까 통과가 되더라. 3시간 살짝 이내에 풀었는데, 이거 현장에서 봤으면 절대 못 풀었을 것 같다.

 

잘못했던 부분은 line 22번 while문. 이거 빼먹어서 도망칠 수 있는 도망자 중 각 좌표에서 1명씩만 움직였다.

 

이상했던 부분은 runner_move() 함수 내 주석처리한 이중for문이었는데... 알고보니 오타였다. y를 x로 잘못 썼는데 이거때문에 1시간 더 날렸다... 제발 현장에서는 이런 실수 하지 말자......

 

술래가 달팽이 모양으로 돌아가는데, 이전에 풀었던 백준 21611 - 마법사 상어와 블리자드 문제에서는 회오리 모양을 일자로 펴놓고 풀었다면, 이번에는 그럴 여건이 안 되어서 직접 달팽이 모양으로 이동하는 걸 구현했다. 사용한 변수가 엄청 많아졌는데...

  - 규칙 상 술래는 센터부터 현재 방향으로 1, 1, 2, 2, 3, 3...칸씩 이동한다.

  - 위의 1, 1, 2, 2, 3, 3...을 tag_max_move에 저장한다고 했을 때, 현재 방향으로 연속해서 이동한 횟수인 tag_cur_move가 tag_max_move에 도달할때마다 0으로 초기화시켜주고, 방향 전환을 해야한다.

  - 함수 하나로 안에서 바깥으로, 바깥에서 안으로 오는 걸 구현하려면 이거 체크하는 flag를 또 달아줘야 한다.

 

이렇게 구현하는게 맞나...? 이 부분 구현할 때는 실수 없이 한 번에 제대로 구현하긴 했는데, 너무 복잡하다는 느낌은 지울 수가 없다. 어차피 좌표 (y,x)에서는 무조건 정해진 방향대로만 움직이니까, n이 크지 않다면 n*n matrix 파두고 안->바깥, 바깥<-안일 때 해당 좌표에서 어느 방향으로 이동해야 하는지 미리 만들어두고 코드 짜도 될 것 같고...

 

	def move(y, x, d, flag, tmp_field): # 개별 도망자 이동
	next_y, next_x = y+dir[d][flag][0], x+dir[d][flag][1]
	if not(0 <= next_y < n) or not(0 <= next_x < n): # 격자 밖으로 나가는 경우
	flag = (flag+1)%2 # 방향 전환
	next_y, next_x = y+dir[d][flag][0], x+dir[d][flag][1] # 반대 방향 1칸 앞으로
	if next_y == tag_y and next_x == tag_x: # 술래가 그곳에 있다면
	tmp_field[y][x].append([d, flag]) # 원래 위치 유지(방향만 전환)
	else:
	tmp_field[next_y][next_x].append([d, flag]) # 다음 위치 이동
	return tmp_field
	def runner_move(): # 모든 도망자 이동 업데이트
	# 거리 3 이하인 도망자만 이동
	tmp_field = [[[] for _ in range(n)] for _ in range(n)]
	for y in range(tag_y-3, tag_y+3+1):
	for x in range(tag_x-3, tag_x+3+1):
	if abs(tag_y-y) + abs(tag_x-x) <= 3 and (0 <= y < n and 0 <= x < n): # 거리 3 이하, 격자 내부
	if field[y][x][0]: # 도망자가 있다면
	while field[y][x][0]:
	d, flag = field[y][x][0].pop() # 도망자
	tmp_field = move(y, x, d, flag, tmp_field) # 도망자 이동 반영된 tmp_field
	for y in range(tag_y-4, tag_y+4+1): # 도망자가 이동한 위치 최대 4칸 거리 가능
	for x in range(tag_x-4, tag_x+4+1):
	if 0 <= y < n and 0 <= x < n: # 격자 내
	if tmp_field[y][x]: # 이동한 도망자가 존재
	field[y][x][0] += tmp_field[y][x] # 업데이트
	return
	def tag_move(): # 술래 이동
	global tag_y, tag_x, tag_cur_move, tag_move_flag, tag_max_move, tag_ccw_move, tag_d
	tag_y += tag_dir[tag_d][0]
	tag_x += tag_dir[tag_d][1]
	if (tag_y == 0 and tag_x == 0) or (tag_y == n//2 and tag_x == n//2): # 센터 혹은 좌상단 끝
	tag_d = (tag_d+2)%4
	# tag_max_move: 그대로
	if tag_y == 0:
	tag_cur_move = 1
	tag_move_flag = True
	else:
	tag_cur_move = 0
	tag_move_flag = False
	tag_ccw_move = (tag_ccw_move+1)%2
	return
	tag_cur_move += 1
	# 시계/반시계 방향 따른 방향 전환
	if tag_max_move == tag_cur_move:
	tag_cur_move = 0
	if tag_ccw_move: # 센터 가는 방향
	tag_d = (tag_d-1)%4
	if tag_move_flag: # n칸 이동 2번 했음
	tag_max_move -= 1
	else:
	tag_d = (tag_d+1)%4
	if tag_move_flag: # n칸 이동 2번 했음
	tag_max_move += 1
	tag_move_flag = (tag_move_flag+1)%2 # n칸 이동 몇 번 했는지 업데이트
	return
	def runner_check(): # 잡을 수 있는 도망자
	global sol, m
	tmp_y, tmp_x = tag_y, tag_x
	for r in range(3):
	if 0 <= tmp_y < n and 0 <= tmp_x < n: # 격자 내부
	if field[tmp_y][tmp_x][0] and (field[tmp_y][tmp_x][1] == 0): # 도망자가 있는데 나무 없으면
	sol += turn*(len(field[tmp_y][tmp_x][0]))
	m -= len(field[tmp_y][tmp_x][0])
	field[tmp_y][tmp_x][0] = []
	tmp_y += tag_dir[tag_d][0]
	tmp_x += tag_dir[tag_d][1]
	return
	if __name__ == "__main__":
	n, m, h, k = map(int, input().split())
	field = [[[[], 0] for _ in range(n)] for _ in range(n)] # 도망자, 나무 위치
	dir = [[[0, -1], [0, 1]], [[-1, 0], [1, 0]]]
	for _ in range(m):
	x, y, d = map(int, input().split())
	field[x-1][y-1][0].append([d-1, 1]) # [0: 좌우, 1: 상하], 1: 우/하
	for _ in range(h):
	x, y = map(int, input().split())
	field[x-1][y-1][1] = 1 # 나무 위치
	sol = 0
	tag_y, tag_x = n//2, n//2 # 술래 초기 위치
	tag_dir = [[-1,0], [0,1], [1,0], [0,-1]] # 상우하좌(초기 방향), 반대로 틀면 센터로 가는 방향
	tag_d = 0 # 방향 지정
	tag_max_move = 1 # 현재 방향으로 최대 몇 칸 이동할 수 있는지
	tag_cur_move = 0 # 현재 방향으로 연속 몇 칸 이동했는지
	tag_move_flag = False # 1,1,2,2,3,3... 칸 주어진 방향대로 이동하는 규칙 체크(False: 최대 n번 이동 처음)
	tag_ccw_move = False # True: 센터에서 바깥쪽으로 방향
	for turn in range(1, k+1):
	runner_move()
	tag_move()
	runner_check()
	if m == 0:
	break
	print(sol)

view raw 술래잡기.py hosted with ❤ by GitHub