• 프로그래머스 블록이동하기
• 이코테 책 355p

문제

입출력과 제한

• 제한
  • 1초 / 128MB
• 입력예시
  • [[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]]
  • 로봇이 오른쪽으로 한칸 이동후, (1,3)칸을 축으로 반시계방향 90도회전
  • 아래쪽으로 세칸 이동하면 (4,3),(5,3) 두 칸 차지함
  • 이제 (5,3) 축으로 시계방향으로 90도호전
  • 오른쪽으로 한칸 이동하면 (N,N)에 도착
• 출력예시
  • 7
  • 따라서 목적지 도달하기까지 최소 7초

상황

• 0=빈칸 / 1=벽
• 아놔 너무 쓰기에 복잡한테 책/프로그래머스를 직접 참고하세요

풀이

처음 든 생각

이동방법이 특이할 뿐이지, 최소경로로 목적지까지 가는 BFS 겠다!
근데 이제 구현을 열심히해야지.
이동방법도 dx, dy처럼 움직일 수 있는 방식을 배열로 주고 그 안에서 고르게 하면 될듯한데

접근

이런 바둑판 문제에선, <모든 칸 = 노드 & 모든 노드는 1인 간선으로 연결되어있다> 고 생각하기

간선의 비용이 1로 동일하기때문에, BFS를 사용하여 최적해를 구할 수 있다.

특이사항

• 로봇이 두칸짜리이기때문에, 로봇의 위치정보를 튜플로 관리해야

풀이 디테일

• 이동
  • 상
  • 하
  • 좌
  • 우
• 회전
  • 로봇이 가로로 놓인 상태에서 아래쪽으로 회전
    • 아래쪽에 벽이 없어야
  • 로봇이 가로로 놓인 상태에서 위쪽으로 회전
    • 위쪽에 벽이 없어야
  • 로봇이 세로로 좋인 상태에서 오른쪽으로 회전
    • 오른쪽에 벽이 없어야
  • 로봇이 세로로 놓인 상태에서 왼쪽으로 회전
    • 왼쪽에 벽이 없어야
• padding
  • map의 외곽에 1(벽)으로 패딩을 두르면, 로봇이 맵을 벗어나지 않는지 판정하기 더 간단하다
• 코드를 간단히 하기 위해 함수로 잘 나누기

코드

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,0,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]

	# 너비 우선 탐색 BFS 수행
	q = deque()
	visited = []
	pos = {(1,1),(1,2)} # 시작 위치 설정
	q.append((pos, 0))
	visited.append(pos) # 방문처리
	# 큐가 빌때까지 반복
	while q :
		pos, cost = q.popleft()
		# (n,n) 위치에 로봇이 도달했다면, 최단 거리이므로 반환
		if (n,n) in pos :
			return cost
		# 현재 위치에서 이동할 수 있는 위치 확인
		for next_pos not in visited :
			q.append((next_pos, cost+1))
			visited.append(next_pos)
	return 0

느낀점

왕 .. 엄청 복잡하다
그래도

• padding 둘러서 계산 간단하게 하지
• 함수로 빼서 최대하 간결하게 하기

는 책에 적힌대로 유용하고 더 간단하게 푸는 좋은 방법이었다.

• BFS에서 next_pos를 원래는 간단하게 4방으로만 움직일땐 간단했는데,
  오히려 복잡하게 움직이고 복잡한 위치를 유지하니까
  BFS는 1 만큼 움직일 수 있는 모든 node를 큐에 담아둔다. 다 담은 후에 차례대로 방문한다 라는 개념이 오히려 더 잘 머리에 박히게 됐다.
  그래서 오히려 '갈수있는 곳은 다 큐에 담고보자' 라는 생각으로 코드를 짜니까 한결 코드가 잘 이해되는 기분이었다.