[Programmers] 리틀 프렌즈 사천성

알고리즘/programmers

꾸준함. 2022. 7. 9. 11:16

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

BFS 알고리즘을 이용하여 풀 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. State 구조체는 좌표, 방향을 꺾은 횟수, 그리고 이전 방향을 저장하는 구조체입니다.

2. 전처리를 진행하는데 문제에서 가능한 경우 중 알파벳 순으로 가장 먼저인 케이스를 반환하라고 했으므로 주어진 배열 내 알파벳들을 set 자료구조에 저장해주고 각 알파벳의 위치를 v 벡터에 저장해줍니다.

3. set에 알파벳이 남아있는 한 계속 제거할 수 있는 타일이 존재하는지 확인합니다.

3.1 set을 순회하면서 해당 타일을 제거할 수 있는지 확인하고 제거할 수 있을 경우 해당 타일을 '.'으로 바꿔준 후 다시 3번을 반복합니다.

3.2 현재 상태에서 제거할 수 있는 타일이 없을 경우 불가능한 경우이므로 "IMPOSSIBLE"을 반환합니다.

4. 사천성을 클리어했을 경우 answer를 반환해줍니다.

개발환경: Programmers IDE

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

꾸준함