Enochkon's blog

문제

코드

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을 출력한다.

문제

코드

from collections import deque 

def solution(maps):
    maps = [list(_) for _ in maps]
    rows, cols = len(maps), len(maps[0])
    distance = [[-1 for _ in range(cols)] for _ in range(rows)]
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'L':
                q.append((i, j, 0))
                distance[i][j] = 0
    while q:
        cx, cy, dist = q.popleft()
        
        for dx, dy in d:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < rows and 0 <= ny < cols and maps[nx][ny] != 'X' and distance[nx][ny] == -1:
                distance[nx][ny] = dist + 1
                q.append((nx, ny, dist + 1))
                
    l_dist, e_dist = -1, -1
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'S' and l_dist == -1:
                l_dist = distance[i][j]
            if maps[i][j] == 'E':
                e_dist = distance[i][j]
    
    if l_dist == -1 or e_dist == -1:
        return -1
    else:
        return l_dist + e_dist

풀이

• 시작지점부터 레버까지, 그리고 레버부터 탈출지점까지의 거리를 구해라

1. 입력받은 문자열을 리스트형태로 변환
2. 거리를 입력할 배열 구현
3. 시작지점부터 바로 탈출지점까지 가는게 아닌 중간에 레버를 올려야하므로 레버를 기준으로 시작지점과 탈출지점의 최단거리를 구하면 된다고 생각
   1. bfs를 활용해 레버의 위치인 ‘L’부터 시작, 전체 미로의 거리를 L을 기준으로 기입
   2. 거리를 입력한 distance 배열에서 시작지점인 S와 탈출지점인 E의 좌표에 대한 거리의 합을 출력
   3. 만약 하나라도 -1인 경우 길이 없는것이므로 -1 출력

특이사항

• 출발 지점부터 레버까지와 레버부터 도착 지점까지의 길이 중복되도 된다길래 어떻게 구현해야할지 생각하다가, 두번의 bfs를 돌리면 되겠다고 생각했다. → 하지만 이렇게 구현할 경우 낭비가 심하다고 생각. → 중간 지점인 레버를 기준으로 거리를 구하면 bfs를 한번만 돌릴 수 있다고 생각 후 구현

문제

코드

def solution(dirs):
    answer = 0
    num = {'U':(0,1),'D':(0,-1),'R':(1,0),'L':(-1,0)}
    res={}
    visited = set()
    x, y = 0, 0

    for i in dirs:
        nx, ny = x + num[i][0], y + num[i][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            if ((x, y), (nx, ny)) not in visited:
                answer += 1
                visited.add(((x, y), (nx, ny)))
                visited.add(((nx, ny), (x, y)))
            x, y = nx, ny

    return answer

풀이

• 중복을 제외하고 방문한 선분을 체크하기

1. 입력받는 문자열에 따라 이동하는 좌표값 딕셔너리를 구현.
2. 입력에 따라서 x,y를 움직인다. -5 ~ 5의 범위는 넘어가면 continue 해준다,
3. set()에 이동좌표를 넣어서 만약 그 좌표가 존재하지 않으면 answer+=1해주고, 존재하면 중복한 값이라고 판단하고 넘어간다.