📍 이것이 코딩테스트다(나동빈) - part3.알고리즘 유형별 기출문제 를 풀고 기록했습니다.

1. 뱀

백준 링크 : https://www.acmicpc.net/problem/3190

1.1 내 풀이

• 틀림.
• 뱀 위치는 1, 사과 위치는 9로 표시
• 꼬리를 잘못 처리함.
  - new_r = now_r + dr[direction]에서 now를 꼬리라고 생각함. (뱀 길이가 2 이상이 될 때 오류남)
  - 대신 뱀의 머리부터 꼬리를 큐로 저장해서 가장 먼저 들어간 좌표를 꼬리로 처리해야함.
• 방향 변환 정보인 for l in turn을 씌워서 중단하는 조건(벽을 마주치거나 자기자신의 몸과 부딪혀서)에서 break가 애매했음. (if result != 0: break). 책 답안처럼 '방향 변환하는 부분'과 '중단 조건에 해당하지 않으면 전진'을 구분해야할 것 같다.

n = int(input())
board = [[0]*(n+1) for _ in range(n+1)]

k = int(input()) # 사과 개수
for _ in range(k):
  a, b = map(int, input().split())
  board[a][b] = 9 # 사과 위치는 9로 표시

l = int(input()) # 변환횟수
turn = []
for _ in range(l):
  x, c = input().split()
  turn.append((int(x), c))


# 방향
dr = [0, 1, 0, -1] # 오른쪽, 아래, 왼쪽, 위
dc = [1, 0, -1, 0]

# 회전 전까지 이동
def forward(now_r, now_c, direction, t):
  if (now_r == 0 | now_c == 0) | (now_r == n+1 | now_c == n+1) : # 벽과 부딪히면
    print('ceil!')
    return False
  if board[now_r][now_c] == 1: # 자기자신과 부딪히면
    return False
  if board[now_r][now_c] != 9: # 사과 없으면
      board[now_r-dr[direction]][now_c-dc[direction]] -= 1 # 다시 0으로
  board[now_r][now_c] = 1 # 사과 없애기
  return t+1


board[1][1] = 1 # 뱀 위치는1로 표시
t = 0 # 시간
now_r, now_c = 1 , 1 # 뱀 머리
direction = 0 # 처음에 오른쪽으로 이동
result = 0

for l in turn:
  if result != 0:
    break
  while t < l[0]: 
    now_r += dr[direction]
    now_c += dc[direction]
    new_t = forward(now_r, now_c, direction, t) 
    print(now_r, now_c)
    print(new_t)

    if not new_t : 
      print('t', t)
      result = t
      break
    else:
      t = new_t

  # 회전
  if l[1] == 'D':
    direction += 1
  else:
    direction -= 1
  direction %= 4

print(result)

1.2 책 답안

• nx = x + dx[direction]해놓고, 중단되지 않을 때 x, y = nx, ny

n = int(input())
data = [[0]*(n+1) for _ in range(n+1)]
k = int(input()) # 사과 개수
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] == 0:
        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())

• 뱀의 몸통을 data[nx][ny] == 2으로 처리하지 않더라도 그냥 큐를 이용해도 될 것 같음

n = int(input())
k= int(input())

data = [[0]*(n+1) for _ in range(n+1)]
for i in range(k):
  # 사과가 있는 곳은 1로 표시
  a, b = map(int, input().split())
  data[a][b] = 1

l = int(input())
info = []
for i in range(l):
  a, b = input().split()
  info.append([int(a), b])

# 동 남 서 북
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
direction = 0

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

x, y = 1, 1
q = []
q.append((x, y))
time = 0 # 시간
index = 0

while True:
  nx = x + dx[direction]
  ny = y + dy[direction]
  if nx >= 1 and nx <= n and ny >= 1 and ny <= n and (nx, ny) not in q:
    q.append((nx,ny))
    # 사과가 없으면
    if data[nx][ny] != 1:
      px, py = q.pop(0)
      data[px][py] = 0

  else:
    time += 1
    break
  x, y = nx, ny
  time += 1
  if index < l and time == info[index][0]:
    direction = shift_direction(direction, info[index][1])
    index += 1
print(time)