백준 #3190

문제

백준 3190번: 뱀

내 코드

from collections import deque
import sys

n = int(sys.stdin.readline())
k = int(sys.stdin.readline())


apples = [[0]*n for i in range(n)] # 사과 위치 저장 n*n 배열
for i in range(k):
  row, col = map(int, sys.stdin.readline().split())
  apples[row-1][col-1] = 1 # 사과 위치에 1 할당

l = int(sys.stdin.readline())
directions = {} # 시간-방향 딕셔너리에 저장
for i in range(l):
  temp =  sys.stdin.readline().split()
  key = int(temp[0])
  value = temp[1].strip()
  directions[key] = value
  
dx = [-1,0,1,0] # 하, 우, 상, 좌
dy = [0,1,0,-1]

cnt = 0
cx, cy = 0,0
snakeDir = 1
snake = deque()
snake.append((cx,cy)) # 처음 위치 (0,0) 넣어놓고 시작

def change_dir(snakeDir, dir):  
  # 뱀 방향, directions의 L,D 에 따라 뱀 방향을 업데이트
  # Down: 0, Right:1, Up:2, Left:3
  if dir is None:
    return snakeDir
  if dir == 'L':
    snakeDir = (snakeDir-1)%4
  else:
    snakeDir = (snakeDir+1)%4
  return snakeDir

while True:
  cnt +=1

  # 이동 시도
  nx = cx+dx[snakeDir]
  ny = cy+dy[snakeDir]

  # 이동 실패 케이스 확인
  if nx<0 or nx>=n or ny<0 or ny>=n:
    break
    
  isExist = False
  for s in snake:
    if (nx,ny) == s:
      isExist = True
      break
  if isExist:
    break
    
  # 이동 성공 시
  snake.appendleft((nx,ny)) # queue에 새 위치를 추가
  if apples[nx][ny]==0: # 새 위치에 사과 없으면 queue 첫 원소 삭제
    snake.pop()
  else:
    apples[nx][ny]=0

  cx, cy = nx, ny

  # 이동 후 방향 전환
  dir = directions.get(cnt)
  snakeDir = change_dir(snakeDir, dir)  

print(cnt)

해결 방식을 생각하는 게 어렵다기보다는 구현이 까다로웠던 문제

뱀을 queue로 생각했다.
뱀이 한 칸 이동 = queue에서 pop() , append(새 위치)

코드 깔끔해서 좀 마음에 든다. 다양한 자료구조를 잘 활용했다는 점도~!

1. 이동 시도
   : 현재 방향을 확인해 새로운 위치를 구한다.
2. 이동 실패 케이스 확인
   • 보드판을 벗어난 경우
   • 자기자신과 부딪힌 경우 : queue에 (nx,ny)가 있는지를 확인
3. 실패 케이스에 해당될 경우 게임 종료, 아닐 경우 (nx,ny)에 사과가 있는지 확인
4. (nx,ny)에 사과가 있을 경우 pop없이 append, 없을 경우 pop후 append
5. directions 딕셔너리에 현시점 cnt에 해당하는 key값이 있는 경우 방향 전환
6. cnt 증가

• 뱀이 모든 칸을 다 채워도 queue의 최대 길이가 100이므로 queue를 for문으로 돌며 검사하는 게 시간복잡도 측면에서 그렇게 큰 문제는 되지 않을거라 생각했다.

딕셔너리 활용

딕셔너리를 처음 써봤당. (추천해준 deque께 감사) 이 친구 Iteration을 제외한 모든 연산의 Big-O가 O(1)이다! 대박 🙊

• 문제에서 주어진 (a,b) 형식의 값을 저장하고 싶은데 a값이 unique한 경우
• 서로 짝지어진 두 값이 있고, 그 중 한 값으로 그에 상응하는 다른 값을 조회하고 싶은 경우

리스트에 튜플을 담는 형식, [0]*n 배열을 선언해 인덱스a에 b를 저장하는 방식보다 효율적이다.
리스트에 튜플 담는 건 Iteration할 때 튜플에서 또다시 인덱싱을 해줘서 매우 성가시고, [0]*n은 어찌됐든 메모리 낭비가 있는거니까.

딕셔너리 컴프리헨션

이 문제 입력 특성(한 줄에 문자열과 숫자가 같이 있음) 때문에 사용하진 않았지만, 리스트 컴프리헨션처럼 딕셔너리 컴프리핸션도 가능하다.

>>> students = ['철수', '영희', '길동', '순희']
>>> { student: 0 for student in students }
{'철수': 0, '영희': 0, '길동': 0, '순희': 0}

콜론(:)을 잘 사용해주면 된다.

Javascript의 map함수처럼 딕셔너리의 모든 원소를 돌면서 특정 값만 필터링하는 것도 가능하다.

scores = {'철수': 50, '영희': 80, '길동': 90, '순희': 60, '전학생': 100}
scores = { name: score for name, score in scores.items() if name != '전학생'}
print(scores)

{'길동': 90, '순희': 60, '영희': 80, '철수': 50}

grades = { name: 'PASS' if value > 70 else 'No-PASS' for name, value in scores.items()}
# name, value는 각각 key, value에 해당하는 변수명으로 내가 원하는대로 작성해주면 된다.
print(grades)

{'길동': 'PASS', '순희': 'No-PASS', '영희': 'PASS', '철수': 'No-PASS'}

특정 Key값의 존재 여부 조회하기

크게 두 가지 방법으로 value를 조회할 수 있다.
1. dict[key] : 바로 인덱싱하기
2. dict.get(key) : get() 사용하기

다만 바로 인덱싱하는 방법은 존재하지 않는 Key값을 조회하는 경우, 코드가 그대로 종료된다.
따라서 get을 사용하는 편이 좋다. get으로 조회하면 key가 없을 때 코드가 종료되는 게 아니라 None을 반환한다. is None 연산자를 사용해 key가 없는 케이스를 확인할 수 있다.

출력하기

print(*dict)
하면 딕셔너리의 모든 key값을 공백으로 연결해 출력할 수 있다.