[Python] 리코쳇 로봇

Saemi Min·2023년 3월 22일
0

Programmers Algorithm

목록 보기
29/29
post-thumbnail

문제

해당 문제 링크

정답

## 리코쳇 로봇

from collections import deque

def solution(board):
    
    n=len(board)
    m=len(board[0])
    
    for i in range(n):
        for j in range(m):
            if board[i][j]=='R':
                a, b = i, j
    
    #상 하 좌 우
    dx = [-1, 1, 0, 0] #행 이동
    dy = [0, 0, -1, 1] #열 이동
    

    # v = [[0]*len(board[0])]*len(board) #이렇게 작성하면 XX
    v = [[0]*m for _ in range(n)]

    def bfs(x, y):
        q=deque()
        q.append((x, y))
        v[x][y]=1
        
        while(q):
            x, y=q.popleft()
            
            for i in range(4): 
                nx, ny = x, y #처음 정해진 길로 쭈욱 미끄러지기 때문에 while문에서는 처음 큐에서 들어가는 값에서 시작해서 한 방향으로 가게

                if board[nx][ny]=='G': #while문 안쪽에 못넣는 이유는 while에서는 일단 한칸씩 이동하는걸로 되는데 쭈욱 미끄러지다가 멈추는 곳에서 도착했는지를 봐야하는데 while문안에 있으면 그렇지 못하기 때문이다.
                            return v[x][y]
                while(1):    
                    nx=nx+dx[i] #nx = x+dx[i]이 안되는 이유) 한 방향으로 쭉 미끄러져야 하기 때문에
                    ny=ny+dy[i]

                    if nx>=n or nx<0 or ny>=m or ny<0: #판을 나갔을 때
                        nx-=dx[i]
                        ny-=dy[i]
                        break

                    if board[nx][ny]=='D' : #장애물을 만났을 때
                        nx-=dx[i]
                        ny-=dy[i]
                        break
                    
                if not v[nx][ny]: #쭉 미끄러지고 나서 그 지점을 체크해서 +1을 더해주는 것이다.
                    v[nx][ny]=v[x][y]+1
                    q.append((nx, ny))
        return -1

           
    result=bfs(a, b)
    if result>0:
         return result-1

    return result               
            

어떻게 이렇게 풀었고, 필자가 처음 접근했던 실수를 알고 싶다면 풀이를 천천히 읽어나가는 것을 추천한다..


풀이

문제를 풀면서 겪었던 코드 문제나 실수

1. 리스트 초기화 (2차원 리스트)

코드를 보면 알수 있듯이 위와 같이 작성하면 안된다.

    v = [[0]*len(board[0])]*len(board) #이렇게 작성하면 XX
    
    v = [[0]*m for _ in range(n)]

위와 같이 작성하면 모든 행이 같은 객체로 인식된다.

이러한 문제가 발생한다.
참고 사이트


2. 내부 while(1)문

잘못된 접근 및 코드

안에 while문으로 돌리는 것은 접근했고 그렇게 풀고자 했다.
처음 접근 방식은 방문 표시하는 배열 v에 값을 넣어주는 것이 아닌 k라는 임의의 변수에 미끄러진 뒤 횟수를 1씩 더해줘서 결론적으로 k의 값을 반환하는 것이었다. 하지만 여기서 빠트린 것은
처음 while(q) 안의 for문으로 상, 하, 좌, 우를 모두 움직인다는 경우의 수가 있다는 것이다. 이를 해결해줄 수 없는 코드였다. 부딪히면 부딪히 전의 위치에서 시작하는 것으로 하는 접근은 맞았지만 코드 순서에서도 잘못 작성하였다. 아래 코드가 처음 작성한 잘못된 코드이다.

    def bfs(x, y):
        k=1
        q=deque()
        q.append((x, y))
        v[x][y]=1
        print(q)
        
        while(q):

            d=q.popleft()
            x=d[0]
            y=d[1]
            
            for i in range(4):
                
                while(1):    
                    nx=x+dx[i]
                    ny=y+dy[i]
                    print(dx[i], dy[i])
                    print(nx, ny)

                    if board[nx-dx[i]][ny-dy[i]]=='G':
                            print("찾음")
                            print(k)
                            return k

                    if board[nx][ny]=='D' : #장애물을 만났을 때
                        if board[nx-dx[i]][ny-dy[i]]=='G':
                            print("찾음")
                            print(k)
                            return k
                        print("장애물")
                        q.append((nx-dx[i], ny-dy[i]))
                        v[nx][ny]=1
                        k+=1
                        print(v)
                        break
                        
                    if nx>=len(board) or nx<0 or ny>=len(board[0]) or ny<0:
                        print("나감")
                        q.append((nx-dx[i], ny-dy[i]))
                        k+=1
                        print(v)
                        break
                    
                    if board[nx][ny]=='.' or board[nx][ny]=='R' or board[nx][ny]=='G' and v[nx][ny]==0: #빈공간일때
                        print("빈공간")
                        print(nx, ny)

                        if board[nx+dx[i]][ny+dy[i]]=='D':
                            print("다음 장애물 있음")
                            v[nx][ny]=1
                            
                            q.append((nx, ny))
                            break
                            # if v[nx][ny]:
                            #     break
                            
                            
                            print(v)
                            continue

                        v[nx][ny]=1
                        x=nx
                        y=ny
                        continue
                    else: #
                        x=nx
                        y=ny
                        break

그래서 고쳐야 할 부분이 많다.
코드 주석으로 무엇을 고려해서 고쳤는지, 이렇게 작성한 이유를 정답 코드에 적어놨다.
하나씩 살펴보고자 한다.


1) 이 코드는 처음 원래 while(1) 내부에 넣어놨었다. 하지만 밖으로 빼는 것이 맞다.
while문 안쪽에 못넣는 이유는 while에서는 일단 한칸씩 이동하는걸로 되는데 쭈욱 미끄러지다가 멈추는 곳에서 도착했는지를 봐야하는데 while문안에 있으면 그렇지 못하기 때문이다.

                if board[nx][ny]=='G':
                            return v[x][y]

G를 구분할 때는 부딪힌 이후 그 자리에 G가 있는지를 확인하면 되는 식으로 하여 코드를 짜줘야 한다.

2) 원래 BFS 코드를 보면 nx = x+dx[i]으로 작성한다. 왜냐하면 한 칸씩 움직여서 deque에 넣고 빼서 각 위치에 따라 또 다시 상, 하, 좌, 우를 보기 때문이다. 여기서는 쭉 미끄러지기 때문에 어디에 부딪히지 않는 이상 큐에 값이 들어가지 않는다. x+dx[i]로 하게 되면 처음 R이 있는 곳을 기준으로 값이 더해져 계속 무한 반복으로 돌아가 빠져나오지 못하는 오류가 생긴다. 우리는 한 곳으로 쭉 이동해야 한다. 그렇기 때문에 while문 안에서 계속 기존에 있는 위치(nx,ny)에서 하나씩 옮겨가 더해주고 부딪히면 그때서야 while문을 나가게 되고 마지막에 부딪히기 직전의 위치 값을 큐에 넣어주어 다시 시작하는 것이다.

                nx, ny = x, y #처음 정해진 길로 쭈욱 미끄러지기 때문에 while문에서는 처음 큐에서 들어가는 값에서 시작해서 한 방향으로 가게

...
                    nx=nx+dx[i] #nx = x+dx[i]이 안되는 이유) 한 방향으로 쭉 미끄러져야 하기 때문에
                    ny=ny+dy[i]

3) 이동 횟수 세기
원래 하려고 했던 k값으로만 세서는 안됐다. 앞서 언급한 것처럼 상, 하, 좌, 우 여러 경우의 수에 맞게 k값은 변경되기 때문이다. 심지어 이를 각 경우의 수에 맞춘 4개의 변수를 맞는 것도 옳지 않다. 그렇게 되면 내가 지금 어떤 위치로 움직이고 있는지도 알려주는 코드를 추가적으로 작성해줘야하는 정말 간단하지 않고 더러운 코드로 작성이 되기 때문이다.

                if not v[nx][ny]: #쭉 미끄러지고 나서 그 지점을 체크해서 +1을 더해주는 것이다.
                    v[nx][ny]=v[x][y]+1
                    q.append((nx, ny))

3. 시간 초과 문제

R이 있는 위치를 알기 위해 작성하는 코드 부분이다.
둘 다 시간 복잡도가 O(n^2)으로 같은데 왜 시간 초과 문제가 발생하는지 아직 모르겠다... 아는 사람이 있다면 댓글로 알려주길...(알려주시면 감사하겠습니다ㅎ)

<기존에 작성했던 코드>

index() 의 시간복잡도 : O(n) * for문 : O(n) => O(n^2)

    for i in range(n):
        if not board[i].index('R'):
            continue
        else:
            a=i
            b=board[i].index('R')
            break

<변경한 코드>

이중 for문 => O(n^2)

    for i in range(n):
        for j in range(m):
            if board[i][j]=='R':
                a, b = i, j
profile
I believe in myself.

0개의 댓글