리틀 프렌즈 사천성

유승선 ·2022년 4월 8일
0

프로그래머스

목록 보기
18/48
post-thumbnail

오랜만에 풀어보는 BFS 문제이다. 사실 요즘 코딩알고리즘을 푸는데 있어서 심한 슬럼프가 온거같은 기분이다. 문제를 읽어도 읽은 기분이 안들고 구현하는데 있어서 조금이라도 어려움이 있게 되면 금방 포기하고 답부터 찾을려는 내 모습이 한심하게 느껴지고 그랬지만 앞으로 문제를 천천히 풀다보면은 꼭 나아질거라고 믿는 요즘이다.

이번 문제는 BFS유형의 문제고 문제에 적혀있는 조건처럼 타일을 제거할수있다. 다만 이 문제에서 정말 특이한점은 두개 이하의 수평/수직 선분으로 구성된 부분에서 한번 이하로만 꺾을수있다는 점이다. 추가적으로 제거 할수있는 타일 중 알파벳 순서가 가장 먼저 오는 순으로 제거해야한다는 까다로운점까지 적용 됐기때문에 더 어려운 문제같이 느껴졌다.

이 문제를 해결하기 위해 핵심적으로 풀었어야했던 부분은 바로 "한번 이하로 꺽을수있는 경로" 를 찾는것이다. 경로를 꺾을수 있다는것을 확인할수 있는 방법은 방향성을 고려해야한다는 점이었고 지금 갈려고 하는 direction이 같은 방향인지 아니면 다른 방향인지를 아는점이 중요했다. 그리고 방향성이 바뀌게 되면은 +1을, 만약 두번이 꺾이게 되면은 방향성은 +1이 추가된 2가 되기때문에 이 경우에는 타일 제거 실패라고 생각하면 된다.

이런 방향성을 이용한 문제는 이 전에 풀었던 "빛의 경로 싸이클" 이 있었지만 아쉽게도 bfs가 적용된 문제였기 때문에 조금은 다른 느낌으로 풀었다. 내가 어려워했던 부분중 하나는 알파벳을 순서대로 이용한 지속적인 탐색이었는데 map을 이용해 알파벳을 sorting 한다음에 while 문을 이용하여 맵에서 key를 하나씩 제거할수있는 방법이 있었다.

bfs를 하기전에 알파벳을 map에 넣었고 Pos라는 struct 안에 x좌표와 y좌표 그리고 dir 을 저장하였다. 그리고 true에 지속적인 루핑을 이용하여서 map안에 있는 모든 원소가 사라지는 경우를 성공이라고 보고 답을 리턴했고 어떤 방식으로도 map안에 있는 원소를 제거할수 없는 경우는 return IMPOSSIBLE 을 하였다. bool 문을 이용해서 이런식의 루핑을 할수있는것도 배워야 하는 부분인거같다.

bfs를 이용해서 만약에 제거 가능한 타일 일경우 위치를 리턴하였다.

for문이 좀 주목해야되는 부분인데 처음 struct 에 dir 부분을 -1로 지정했고 dir방향을 계속 업데이트 함으로서 현재 위치하고 있는 Pos의 방향이 몇번이 틀어졌는지 알수있었다.

배운점:
1. 방향성을 이용한 BFS
2. 문제를 끝까지 포기하지 말자

참고 블로그: https://ansohxxn.github.io/programmers/129/

profile
성장하는 사람

0개의 댓글