(프로그래머 > Lv2) 리코챗 로봇

by

프로그램 제작자

코드 중심 개발자를 고용하십시오. 배치 기반 위치 매칭. 프로그래머의 개발자별 프로필에 가입하고 기술 호환성이 좋은 회사와 연결하십시오.

Programmer.co.kr

1. 문제

(기입)

게임 보드의 상태를 나타내는 문자열 배열

  • . : 비어있는 곳
  • D: 장애물
  • R: 로봇의 초기 위치
  • G: 타겟 포인트

(결과)

말이 목표 위치에 도달하는 데 필요한 최소 이동 수를 반환합니다.

2. 해결

BFS로 해결할 수 있는 문제입니다. 🙂

먼저 검색의 시작점과 끝점을 찾아야 합니다.

startX, startY = 0, 0
targetX, targetY = 0, 0
width, height = len(board(0)), len(board)
for x in range(height):
    for y in range(width):
        if board(x)(y)=='R': startX,startY = x,y
        elif board(x)(y)=='G': targetX,targetY = x,y

보드의 장애물에 부딪힐 때까지 또는 맨 끝에 미끄러지는 자신을 본다면,

빵 부스러기가 겹칠 수 있음을 알 수 있습니다.


위의 그림에서와 같이 A지점의 오른쪽과 B지점의 오른쪽으로 이동하는 목표지점은 동일하며,

특정 지점 P에서 D로 이동할 때 통과 지점을 다시 D로 검색할 필요가 없습니다.

이렇게 하려면 Visited 라는 배열을 추가합니다. 

visited = (((False)*4 for _ in range(width)) for _ in range(height))

그런 다음 BFS 알고리즘을 사용하여 검색할 수 있습니다.

3. 코드

파이썬

dx = (-1,0,1,0)
dy = (0,1,0,-1)
def solution(board):
    startX, startY = 0, 0
    targetX, targetY = 0, 0
    width, height = len(board(0)), len(board)
    for x in range(height):
        for y in range(width):
            if board(x)(y)=='R': startX,startY = x,y
            elif board(x)(y)=='G': targetX,targetY = x,y
    
    q = ((startX,startY,0))
    visited = (((False)*4 for _ in range(width)) for _ in range(height))
    while q:
        x, y, time = q.pop(0)
        
        if x == targetX and y == targetY:
            return time
        
        for d in range(4):
            if not visited(x)(y)(d):
                visited(x)(y)(d) = True
                nx, ny = x+dx(d), y+dy(d)
                while 0<=nx<height and 0<=ny<width and board(nx)(ny)!='D':
                    visited(nx)(ny)(d) = True
                    nx, ny = nx+dx(d), ny+dy(d)
                q.append((nx-dx(d),ny-dy(d),time+1))
                
    return -1