프로그래머스: 지게차와 크레인

프로그래머스

 

구현 문제처럼 보이는 BFS 문제였다. 

 

문제 요약

이 문제는 알파벳 블록을 특정 수단을 이용하여 제거하고 남은 컨테이너의 수를 구하는 문제이다.

입력으로는 전체 블록들의 배치와

각 회차별 수단과 제거 알파벳이 주어진다. 

(["A", "BB", "A"])

 

알파벳이 한번만 나오면 지게차를 사용하고 (예시: A)

두번 나오면 크레인을 사용한다. (예시: AA)

 

지게차를 사용할 경우 외부에서 접근 가능한 블록들만 제거가 가능하다. 

단, 순차적으로 지게차를 이용해 제거하고 접근 가능한 블록을 연쇄적으로 제거하는 것이 아닌

각 회차별 딱 그 시점에서 제거 가능한 블록들만 제거 가능하다. 

위와 같은 상황에서 오직 주황색 C만 제거가능하다. 

 

해결 알고리즘

• 크레인을 사용할 경우
  • 해당하는 알파벳 갯수를 세면서 그 자리를 0으로 채워넣는다
• 지게차를 사용할 경우
  • 크레인을 사용했을때 0으로 처리된 부분들이 외부와 연결되는지 확인하는 BFS를 실행한다. - cleanUp
  • 이후 외곽인지 체크 후 0으로 채워 넣으며 갯수를 센다.
    • 외곽인지 체크하는 방법은 위, 아래, 양 옆으로 이동했을 때 외부인지 확인하는 방법을 사용했다.

 

TroubleShooting

여기서 내가 했던 실수는 다음과 같다. 

• BFS 구현시 visited를 queue에서 poll 하자마자 검사하지 않았다는 점
  • 이것이 상당한 성능 저하를 불러왔다. 나는 그 다음 이동할때 검사를 했는데 그렇게 되면 중복처리되는 경우가 발생한다. 

다음과 같은 상황일때, poll 하자 마자 visited 검사를 하지 않으면 두번째 3에서도 주변 탐색을 진행하게 된다.

그럼 불필요한 for문을 돌게 되는것이다.

 

그리고 코드를 더 빠르게 하는 방법은

• String 대신 char 쓰기
• int[] 대신 boolean[] 쓰기 

정도 있을거 같다. 

char를 사용했을때, 모든 초기값은 0이라는 사실을 기억하자.