문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/60063
전형적인 BFS 문제인데 다른 전형적인 문제와 달리 이동하는 블록이 (2 * 1) 칸인 문제였습니다.
회전하는 코드를 좀 더 최적화하면 깔끔할 것 같은데 일단은 구현한 그대로 포스팅했습니다.
추후... 리팩토링 진행하도록 하겠습니다.
알고리즘은 아래와 같습니다.
1. 로봇을 나타내는 블록의 y좌표, x좌표를 나타내는 vector들, 로봇의 방향이 가로인지 세로인지 나타내는 bool형 변수, 그리고 몇 초 지났는지를 나타내는 cnt를 갖는 State 구조체를 선언해줍니다.
1.1 로봇이 회전을 할 때 두 좌표 둘 다 축이 될 수 있으므로 visited 배열을 표시할 때는 양방향으로 표시해줍니다.
2. 초기 좌표인 (0, 0), (0, 1)에서 BFS를 시작합니다.
2.1 문제에서 주어진대로 상하좌우로 움직이고, 회전을 할 수 있다면 양 축을 기준으로 회전도 진행하여 각각 큐에 넣어줍니다.
2.2 로봇이 (N - 1, N - 1)에 도달할 때까지 BFS를 진행합니다.
3. 로봇이 도착점에 최초로 도착했을 때 초를 반환해줍니다.
개발환경: Programmers IDE
지적, 조언, 질문 환영합니다! 질문 남겨주세요~
반응형
'알고리즘 > programmers' 카테고리의 다른 글
[Programmers] 두 큐 합 같게 만들기 (0) | 2022.08.24 |
---|---|
[Programmers] 성격 유형 검사하기 (0) | 2022.08.22 |
[Programmers] 매칭 점수 (0) | 2022.08.15 |
[Programmers] 외벽 점검 (0) | 2022.08.09 |
[Programmers] 공 이동 시뮬레이션 (0) | 2022.08.07 |