728x90
https://school.programmers.co.kr/learn/courses/30/lessons/169199
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
분석
한 번의 이동 : 상, 하, 좌, 우 4방향 중 하나를 선택해 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것
1. 다음 좌표 값을 board 격자 안 장애물이 아닐 때까지 이동 후 지정
2. 방문하지 않았다면 현재 이동수 +1 저장
아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위
. . . D . . R . D . G . . . . . . . D . D D . . . . D . . D . . . . .
4 -1 3 -1 -1 -1 0 -1 -1 2 7 -1 -1 1 5 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
풀이
import sys
from collections import deque
INF=sys.maxsize
dr = [0,0,1,-1]
dc = [1,-1,0,0]
def solution(board):
answer = 0
n,m=len(board), len(board[0])
sr=sc=er=ec=-1
for i in range(n):
for j in range(m):
if board[i][j]=='R':
sr,sc = i,j
elif board[i][j]=='G':
er,ec=i,j
dist = [[-1]*m for _ in range(n)]
dist[sr][sc] = 0
q = deque([(sr, sc)])
while q:
if dist[er][ec] != -1:
return dist[er][ec]
r, c = q.popleft()
for d in range(4):
nr,nc = r,c
while 0 <= nr+dr[d]< n and 0 <=nc+dc[d]< m and board[nr+dr[d]][nc+dc[d]]!='D':
nr, nc = nr+dr[d], nc+dc[d]
if dist[nr][nc]==-1:
dist[nr][nc]=dist[r][c]+1
q.append((nr, nc))
return -1
728x90