so-devlog
🌙
🧩 Problem Solving

[CodeTree] 루돌프의 반란

date
Oct 24, 2023
slug
code-tree-rudolph-rebellion
author
status
Public
category
🧩 Problem Solving
tags
CodeTree
summary
이동할 때 null 처리 잊지 말기!
type
Post
thumbnail
스크린샷 2023-11-13 오후 3.56.28.png

문제 링크

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion/description?page=1&pageSize=20
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
 
 

1. 아이디어

그냥 빡구현…

1. 소 돌진

1-1) 가장 가까운 사람 찾기 : 거리가 가장 가까우면서 r -> c 우선순위로 더 큰 사람
1-2) 그 사람과 가까워지는 방향 찾기(8방 탐색)
1-3) 그 방향으로 이동하기 : 만약 이동한 곳에 사람이 있다면 상호작용
 

2. 각 사람들 돌진

2-1) 기절했거나 이미 게임에서 탈락했다면 무시
2-2) 소에게 가까워지는 방향 찾기(4방 탐색, 상우하좌 우선순위) : 그 방향에 사람이 있다면 무시, 거리가 무조건 가까워져야함
2-3) 그 방향으로 이동하기 : 만약 이동한 곳에 소가 있다면 상호작용
 

3. 남아있는 사람들 점수 부여 : 보드 순회하면서 남아있는 노드에게 1점씩 부여

  • 이동 시 주의 : 아래 세 과정이 모두 일어나야 함
    • 원래 있던 자리 null
    • node.r, node.c 갱신
    • board 새로운 자리에 node 넣기
 
 

2. 자료구조

  • Node class : 산타(사람), 루돌프(소) - r,c,n, isOut, downUntil, score, isCow
  • Node[][] board
  • List<Node> personList : n을 기준으로 오름차순 정렬 필요
  • Node cow
 
 

이전 코드에서 놓친 부분

  1. 소 이동하기 위해 8방탐색할 때 최소 거리 갱신 안해줌 (minDistance = curDistance 를 안하고 넘어감)
  1. 사람 이동시킬 때 null 처리 + 사람의 r, c만 갱신하고, 보드 새로운 위치에 사람 놓는 거 안함(board[ny][nx] = person 안함)
  1. 사람 튕겨질 때 그 전 위치 null 안함
  1. time <= M 해야 하는데 time < M 했음(마지막 턴 안돌고 끝나버림)