카카오 2020기출, 블록 이동하기 파이썬 코드/해설, 까다로운 구현 문제 LV3, 리스트 집합 속도 차이

문제 설명ㄱㄱ

코딩테스트 연습 - 블록 이동하기

대충 맨왼쪽 위의 로봇이 맨오른쪽 아래로 가면 된다. 주어지는 입력은 0과 1로만 이루어진 위 board 하나이다.

 

 

문제 풀이

 

매번 로봇이 움직일 수 있는 케이스를 찾아서 큐에 시간과 함께 넣고 시간순서대로 하나씩 꺼내서 다시 또 움직일 수 있는 케이스를 찾아서 큐에 넣으면 된다. 

 

이 때 주의할 점은,

 

1. 무조건 오른쪽 아래로 가는게 아니라 복잡한 board의 경우 왔다갔다 해야하므로 움직일 때 윗쪽으로 가는 경우도 생각해야 한다.

2. 로봇이 가로로 있는 경우, 세로로 있는 경우 회전방식이 다르므로 따로 처리해줘야한다.

3. N,N까지 가는 최단시간을 찾아야하니까 bfs만 사용할 수 있다

 

라는 세가지이고, 그 외 코딩적으로 주의할 부분은

 

1. 시간이 오래걸리는 케이스가 있어서 collections의 큐를 사용해야한다.

2. 시간이 오래걸리는 케이스가 있어서 리스트가 아닌 set(집합)을 사용해야 한다.

 

이다. 나도 set이 더 시간이 짧게 걸리는건 알지만 효율성검사가 없어서 그렇게 안 했엇는데 통과를 못했다. 다른 분 풀이를 보니 set을 썻길래 나도 그렇게 했더니 정말 놀라울 정도로 시간이 많이 단축돼서 나도 깜짝 놀랐다. 찾아보니 set은 해시테이블 구조라 탐색시간이 O(1)이라고 한다. 

 

 

사실 한 칸만 차지하는 로봇의 움직임같은 경우는 이미 아주아주많은 코딩테스트에서 사람들이 많이 접해봤을 것 같다. 그런데 이 문제가 어려운 이유는 로봇이 두 칸을 차지하기 때문이다 ... ㅅㅂ 개어렵.. 처음에 혼자 풀어보는데 정말 뭐랄까, 이차원 배열이 이렇게 헷갈렸었나 하는 생각이 1분에 한번씩 들었다. 

 

 

이번엔 코드가 없다. 먼저 다른 분꺼를 참고해서 풀었는데, 거의 구조가 비슷하니까 이렇게 풀었다고 봐도 무방하다.

블록 이동하기 - 2020 카카오 공채 (python)

 

이분과 내 차이는, 음.. 나는 confirm 변수명 대신 visited를 사용했다는점, 그리고 이분 코드를 보면 [[1,1], [1,2]]와 [[1,2], [1,1]]이 로봇이 같은 위치임에도 불구하고 두개를 따로 visited에 넣고 있어서 그 부분을 조금 수정했다는 점 정도이다. 

이 분 코드에서 마지막에 nxt not in confirm을 (nxt[1], nxt[0]) not in confirm을 같이 해주면 중복된 부분이 사라질 수 있다. 속도가 살짝 차이 난다. 

 

그런데 나는 저렇게 코딩할 생각을 전혀 못했어서, 진짜 놀랍다고밖에 할 수가 없다. 진짜 깔끔하고, 간단하다. 감탄.