Q22. 블록 이동하기 (카카오 2020 BLIND RECRUIT 기출)
ㅋㅋㅋㅋ.. 오늘 카카오 서류전형 붙어서 코테를 준비해야 된다. 그래서 기출 문제 한 번 쫙 풀어보려고 마음 먹고 이 문제를 보았는데 살짝 희망을 잃었달까..ㅋㅋㅋㅋㅋ 난생 첨보는 까다로운 변형이었다 ㅠㅠ 서류전형 붙는게 아무때나 찾아오는 기회가 아닌데 이번 기회를 놓쳐야하나 하고 오만가지 생각이 다 든다.
코딩테스트 연습 - 블록 이동하기 | 프로그래머스 (programmers.co.kr)
코딩테스트 연습 - 블록 이동하기
[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7
programmers.co.kr
너무 어려워서 어떻게 풀지 감을 못잡았다. (BFS라는 것만 대충 알고 있었다.)
결국 정답을 보고 클론코딩을 했고 정답에서는 이렇게 풀었다.
1. 엣지 처리를 편하게 하기 위해 board 가장자리에 패딩을 적용한다.
2. 로봇의 현재 위치는 집합을 이용해 표현한다. {(pos1_x, pos1_y), (pos2_x, pos2_y)}
집합을 이용하면 이미 방문한 위치 계산이 훨씬 편해진다.
3. BFS를 이용해서 푼다.
4. Queue에 넣을 다음 위치는 노가다로 계산한다. 즉 상하좌우로 이동시켜보기도 하고 지금 로봇이 세로로 있는지 가로로 있는지에 따라 양방향으로 다 회전시켜본뒤 벽이랑 충돌하지 않으면 Queue에 넣기로 하는 것이다. 다른건 다 괜찮은데 이 부분을 구현하는게 참 까다롭다.
from collections import deque
def get_next_pos(pos, board):
next_pos = []
pos = list(pos)
pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(4):
pos1_next_x, pos1_next_y, pos2_next_x, pos2_next_y = pos1_x + dx[i], pos1_y + dy[i], pos2_x + dx[i], pos2_y + dy[i]
if board[pos1_next_x][pos1_next_y] == 0 and board[pos2_next_x][pos2_next_y] == 0:
next_pos.append( {(pos1_next_x, pos1_next_y), (pos2_next_x, pos2_next_y)} )
if pos1_x == pos2_x:
for i in [-1,1]:
if board[pos1_x + i][pos1_y] == 0 and board[pos2_x + i][pos2_y] == 0:
next_pos.append( {(pos1_x,pos1_y), (pos1_x + i, pos1_y)} )
next_pos.append( {(pos2_x, pos2_y), (pos2_x + i, pos2_y)} )
elif pos1_y == pos2_y:
for i in [-1,1]:
if board[pos1_x][pos1_y + i] == 0 and board[pos2_x][pos2_y + i] == 0:
next_pos.append( {(pos1_x, pos1_y), (pos1_x, pos1_y + i)} )
next_pos.append( {(pos2_x, pos2_y), (pos2_x, pos2_y + i)} )
return next_pos
def solution(board):
N = len(board)
new_board = [[1] * (N+2) for _ in range(N+2)]
for i in range(N):
for j in range(N):
new_board[i+1][j+1] = board[i][j]
q = deque()
visited = []
pos = {(1,1), (1,2)}
q.append((pos,0))
visited.append(pos)
while q:
pos, cost = q.popleft()
if (n,n) in pos:
return cost
for next_pos in get_next_pos(pos, new_board):
if next_pos not in visited:
q.append((next_pos, cost+1))
visited.append(next_pos)
return 0
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이거 안 보고 구현하라고 하면 못할거같다 ㅠㅠ
아~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ㅇ미ㅏㄹ너이라먼이ㅏ럼니아러미ㅏㄴ더리ㅏㅁㄴ어리마넣미ㅏㄴ얼미ㅏㄴㅇ러ㅏㅣ
그냥 흔하디 흔한 아무 중소기업에 입사해봤다가 기겁하고 퇴사해본 입장으로서 꼭 훌륭한 인재가 많은 IT기업에 가고 싶다. 이게 그 첫걸음이 되기를.. 2022년 1일 1문제 챌린지 가즈앗 (300문제 풀기!)