[Python] 프로그래머스. 2020 카카오 recruit - 블록 이동하기 (Level 3)

programmers.co.kr/learn/courses/30/lessons/60063

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

Level 3으로 책정된 이유는 아마

복잡한 알고리즘을 쓰는 게 아니라 조건 잘 체크해서 구현하는 문제이기 때문인 것 같다.

작년에 시험볼 때 카카오 문제가 어렵게 느껴졌던 이유는, 시험장에서 제한된 시간 안에 이만큼 구현하는 게 정말 어려웠기 때문이었다.

심지어 시험중일 때에는, 이걸 여유롭게 고민할 마음의 여유도 없었다. 이 문제만 유달리 어려웠던 것도 아니고...

 

 

Python으로 풀 때 내가 사용한 방법은

 

1. 이미 확인한 비행기 좌표는 set으로 저장한다.

 

2. 비행기 좌표는 tuple을 사용했고, 튜플 내의 좌표값은 정렬했다. 예컨대 ( (0,0),(1,0) ) 비행기와 ( (1,0),(0,0) ) 비행기는 튜플 자료구조상으로는 다른 객체이지만, 같은 값으로 취급해야 하기 때문이다.

 

비행기 좌표 저장에 set 자료구조를 사용하기로 했으므로, 좌표값도 튜플로 저장할 수밖에 없었다.

 

• 튜플 값을 리스트로 변경하고 ( [왼쪽 좌표, 오른쪽 좌표] 형태로 재정의)
• sorted()로 리스트를 정렬한다. 정렬 우선순위로는 y좌표 1순위, x좌표 2순위로 두었다. 
• 정렬된 리스트를 다시 튜플로 변환한다.

3. 비행기의 형태 (가로 형태 / 세로 형태)와 회전 기준좌표에 따라 회전방법이 다르다.

• 비행기가 가로일 경우
  회전축에 사용할 좌표를 정하고, 나머지 좌표를 기준으로 y값의 위 / 아래가 0이면 회전할 수 있다.
• 비행기가 세로일 경우
  회전축에 사용할 좌표를 정하고, 나머지 좌표를 기준으로 x값의 위 / 아래가 0이면 회전할 수 있다.

 

 

 

	from collections import deque
	def solution(board):
	def bfs(start):
	queue = deque()
	queue.append((start, 0))
	visited = set()
	while queue:
	coord, cnt = queue.popleft()
	# 현재 비행기 위치좌표 저장
	visited.add(tuple(coord))
	left, right = coord[0], coord[1]
	if right[0] == len(board)-1 and right[1] == len(board)-1:
	return cnt
	## 비행기가 가로로 있는 경우
	if left[0] == right[0]:
	# 왼쪽으로 1 이동
	new_coord = ((left[0], left[1]-1), (left[0], left[1]))
	# 왼쪽으로 1 이동한 좌표가 board 범위 내에 있고, 아직 방문한 좌표가 아니며, board값이 0인 경우
	if 0 <= new_coord[0][1] < len(board) and new_coord not in visited and board[new_coord[0][0]][new_coord[0][1]] == 0:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	# 오른쪽으로 1 이동
	new_coord = ((right[0], right[1]),(right[0], right[1]+1))
	if 0 <= new_coord[1][1] < len(board) and new_coord not in visited and board[new_coord[1][0]][new_coord[1][1]] == 0:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	# 위/아래 이동
	for dy in [-1,1]:
	new_coord = ((left[0] + dy, left[1]), (right[0]+dy, right[1]))
	if 0 <= new_coord[0][0] < len(board) and new_coord not in visited and board[new_coord[0][0]][new_coord[0][1]] == board[new_coord[1][0]][new_coord[1][1]] == 0:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	# 회전
	for dy in [-1,1]:
	# 왼쪽 좌표 기준으로 회전하는 경우
	# 오른쪽 좌표의 위/아래 좌표가 board 범위내에 있고 값이 0일 경우 = 회전이 가능하다.
	if 0 <= right[0] + dy < len(board) and board[right[0]+dy][right[1]] == 0:
	# 새로운 오른쪽 좌표를 생성하고, 정렬해준다
	new_r = (left[0]+dy, left[1])
	new_coord = tuple(sorted([left, new_r], key = lambda x: (x[0],x[1])))
	if 0 <= new_r[0] < len(board) and board[new_r[0]][new_r[1]] == 0 and new_coord not in visited:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	# 오른쪽 좌표 기준 회전
	# 왼쪽 좌표의 위/아래 좌표가 board 범위내에 있고 값이 0일 경우 = 회전이 가능하다
	if 0 <= left[0]+dy < len(board) and board[left[0]+dy][left[1]] == 0:
	new_l = (right[0]+dy, right[1])
	new_coord = tuple(sorted([new_l, right], key = lambda x: (x[0], x[1])))
	if 0 <= new_l[0] < len(board) and board[new_l[0]][new_l[1]] == 0 and new_coord not in visited:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	## 비행기가 세로로 있는 경우
	if left[1] == right[1]:
	# 위로 이동
	new_coord = ((left[0]-1, left[1]),(left[0], left[1]))
	if 0 <= new_coord[0][0] < len(board) and new_coord not in visited and board[new_coord[0][0]][new_coord[0][1]] == 0:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	# 아래로 이동
	new_coord = ((right[0], right[1]), (right[0]+1, right[1]))
	if 0 <= new_coord[1][0] < len(board) and new_coord not in visited and board[new_coord[1][0]][new_coord[1][1]] == 0:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	# 좌우로 이동
	for dx in [-1,1]:
	new_coord = ((left[0], left[1]+dx), (right[0], right[1]+dx))
	if 0 <= new_coord[0][1] < len(board) and new_coord not in visited and board[new_coord[0][0]][new_coord[0][1]] == board[new_coord[1][0]][new_coord[1][1]] == 0:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	# 회전
	for dx in [-1,1]:
	# 위쪽 기준으로 회전
	# 아래쪽 값의 좌/우 좌표가 board 범위 내에 있고, 값이 0일 경우 회전 가능
	if 0 <= right[1] + dx < len(board) and board[right[0]][right[1]+dx] == 0:
	# 변경된 좌표를 생성하고, 정렬해준다.
	new_r = (left[0], left[1]+dx)
	new_coord = tuple(sorted([left, new_r], key = lambda x: (x[0],x[1])))
	if 0 <= new_r[0] < len(board) and board[new_r[0]][new_r[1]] == 0 and new_coord not in visited:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	# 아래쪽 좌표 기준 회전
	# 위쪽 값의 좌/우 좌표가 board 범위 내에 있고, 값이 0일 경우 회전 가능
	if 0 <= left[1]+dx < len(board) and board[left[0]][left[1]+dx] == 0:
	new_l = (right[0], right[1]+dx)
	new_coord = tuple(sorted([new_l, right], key = lambda x: (x[0], x[1])))
	if 0 <= new_l[0] < len(board) and board[new_l[0]][new_l[1]] == 0 and new_coord not in visited:
	visited.add(new_coord)
	queue.append((new_coord, cnt+1))
	return bfs( ((0,0),(0,1)) )

view raw [프로그래머스] 블록 이동하기.py hosted with ❤ by GitHub