728x90
SMALL
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
시간 제한: 1000ms
메모리 제한: 80MB
필요한 변수
- : 체스판의 크기 ()
- : 기사의 수 ()
- : 명령의 수 ()
- graph: L X L 크기의 그래프, 빈 칸/함정/벽인지 기록
- r, c, h, w, k : N번 loop를 돌며 각 기사들의 정보를 입력을 받음
- r, c: i번째 기사들의 초기 위치
- h, w: 초기 위치에서 세로 길이가 h, 가로 길이가 w인 직사각형 형태로 각 기사들의 영역을 의미
- k: 각 기사들의 체력
- i, d: Q번 loop를 돌며 왕의 명령을 기록, i번 기사에게 방향 d로 한 칸 이동하라는 명령
-> Q번 loop를 돌며 왕이 명령을 내릴 때마다 각 기사들을 움직이고 기록해야한다. 처음에는 각 기사들의 움직임이 있을 때 graph에 그 값을 기록하려하였다. 하지만, 왕이 명령을 내리고 기사들이 움직일 때마다 graph의 값을 새로 쓰고, 기존의 값을 원래대로 원복하는 과정이 필요하므로 불필요한 연산이 많이 수행될 것 같다는 생각이 들었다.
따라서, r, c, h, w, k마다 별도의 1차원 리스트를 두어 각 기사별로 값을 기록하였다.
bfs
왕의 명령을 받은 기사가 d 방향으로 이동 가능하다면 기사들을 연쇄적으로 민다. 각 기사들은 밀릴 수 있는지 조건을 확인하고, 밀릴 수 있다면 루프를 돌며 변수들을 업데이트해주어야한다. 밀림이 가능한 기사들을 기록하고, 필요한 로직을 수행하기 위해 queue 자료구조를 사용하였다.
728x90
LIST
