Enochkon's blog

문제

코드

from collections import deque
def bfs(n):
    q = deque([(n, 0)])
    visited = set([n]) 
    while q:
        cur, count = q.popleft()
        if cur == 1:
            return count
        if cur % 3 == 0 and (cur // 3) not in visited:
            q.append((cur // 3, count + 1))
            visited.add(cur // 3)
        if cur % 2 == 0 and (cur // 2) not in visited:
            q.append((cur // 2, count + 1))
            visited.add(cur // 2)
        if (cur - 1) not in visited:
            q.append((cur - 1, count + 1))
            visited.add(cur - 1)
    return -1  
n=int(input())
print(bfs(n))

풀이

1. n을 입력받는다.
2. 입력받은 n을 bfs함수에 넣고 돌려준다. 문제에서 주어진 조건을 만족하면 q에 넣는다.
   • X가 3으로 나누어 떨어지면, 3으로 나눈다.
   • X가 2로 나누어 떨어지면, 2로 나눈다.
   • 1을 뺀다.
3. 단 n의 크기가 최대 10^18로 엄청 크다. 그러므로 최대한 중복된 값을 탐색하지 않기 위해서 visited라는 set()을 선언한다.
4. 매번 얻는 값들을 visited에 넣어주고, bfs 시행 시 조건을 만족해도 visited에 있는 수들은 q에 넣지 않는다.(중복을 피한다)
5. 1이 되면 횟수를 return한다.

문제

코드

from collections import deque 

def solution(board):
    answer = 0
    board = [list(_) for _ in board]
    row, col = len(board), len(board[0])
    res = [[0 for i in range(len(board[0]))] for j in range(len(board))]
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    
    def slide(i,j,dr,dc):
        while True:
            ci,cj = i + dr, j + dc
            if not (0 <= ci < row and 0 <= cj < col) or board[ci][cj] == 'D':
                return ci-dr, cj-dc
            i,j=ci,cj
                
    for i in range(row):
        for j in range(col):
            if board[i][j]== 'R':
                q.append((i,j,0))
    while q:
        cx, cy, dist = q.popleft()
        res[cx][cy]=dist
        if(board[cx][cy]=='G'):
            answer=dist
            break
        for dr , dc in d:
            nx,ny=slide(cx,cy,dr,dc)
            if(res[nx][ny]==0):
                res[nx][ny]=1
                q.append((nx,ny,dist+1))
    
    if(answer==0):
        return -1
    else:
        return answer

풀이

• 리코쳇 로봇 최소 경로 찾기

1. 문자열을 리스트화 시켜준다.
2. 시작지점 R 부터 목적지 G 지점까지 도달하는 경로를 찾는다.
   1. BFS를 사용한다.
   2. 한칸씩 이동시키는 것이 아닌 slide 함수를 사용해서 진행방향에 벽 혹은 끝까지 진행하는 좌표를 얻는다.
   3. 해당 좌표를 지나간적이 없으면 q에 추가해준다.
   4. 만약 현재 좌표가 ‘G’면 answer에 거리를 추가한다
3. 모든 탐색이 끝난 후 answer이 0인 경우에는 경로를 못찾은것이기 때문에 -1을 아니면 answer을 출력한다.