[Programmers] 블록 이동하기

문제 링크입니다: 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

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~