구현) 뱀

Yona·2022년 2월 16일

구현 백준 알고리즘

👩‍🎓 이것이 코딩 테스트다

목록 보기

26/27

이코테 책
백준 3190

문제

풀이

처음보고 든 생각

있는 그대로 짜면 안되남

풀이아이디어

바둑판 시뮬레이션을 구현을 있는 그대로 짜면 된다 ( dx,dy 이용)

있는 그대로 (특히 순서) 차근차근 구현하면 된다

풀이 아이디어 상세

뱀이 위치하고 있는 정보를 담는데 큐를 사용했다.
- 꼬리와 머리가 하나씩 움직일 수 있다는 것에서 유리하다!
- 첨 생각했을때, 리스트로 위치정보 기록해두는거 생각했는데
  리스트보다 큐가 유동적으로 넣고 빼고 하는게 (이런상황에선) 훨 편하고 코드도 단순해졌다. 오옹

코드

n = int(input())
k = int(input())
data = [[0] * (n+1) for _ in range(n+1)] # 맵정보
info = [] # 방향 회전 정보

# 맵 정보 (사과 있는 곳은 1로 표시)
for _ in range(k) :
	a,b = map(int, input().split())
	data[a][b] = 1

# 방향 회전 정보 입력
l = int(input())
for _ in range(l) :
	x,c = input().split()
	info.append(int(x), c)

# 처음에는 오른쪽을 보고 있으므로 (동,남,서,북)
dx = [0, 1, 0, -1]
dy = [1,0,-1,0]

def turn(direction, c) :
	if c == 'L' :
		direction = (direction - 1) % 4
	else :
		direction = (direction + 1) % 4
	return direction

def simulate() :
	x, y = 1, 1 # 뱀의 머리 위치
	data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
	direction = 0 # 처음에는 동쪽을 보고 있음
	time = 0 # 시작하고 지난 '초' 시간
	index = 0 # 다음에 회전할 정보
	q = [(x,y)] # 뱀이 차지하고 있는 위치 정보(꼬리가 앞쪽)
	while True :
		nx = x + dx[direction]
		ny = y + dy[direction]
		# 맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
		if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2 :
			# 사과가 없다면 이동 후에 꼬리 제거
			if data[nx][ny] = 2
			q.append((nx, ny))
			px, py = q.pop(0)
			data[px][py] = 0
			# 사과가 있다면 이동 후에 꼬리 그대로 두기
			if data[nx][ny] == 1  :
				data[nx][ny] = 2
				q.append((nx, ny))
		# 벽이나 뱀의 몸통과 부딪혔다면
		else :
			time += 1
			break
		x, y= nx, ny #다음 ㅜ이치로 머리를 이동
		time += 1
		if index < l and time == info[index][0] : #회전할 시간인 경우 회전
			direction = turn(direction, info[index][1])
			index += 1
	return time

print(simulate())