[BFS] 프로그래머스 Lv3 블록 이동하기

📌 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

 

 

❗️ Issue 

1. 두개의 블록을 어떻게 visited처리할 것인가

2. 이문제를 처음 봤을 때  DFS+백트래킹으로 생각했다 왜냐하면 모든 경우의 수를 해보고 갔다 백했다하면서
최소 시간을 구한다고 생각해서 약간 swea의 프로세서 연결하기 류의 문제라고 생각했음

3. 가로 일때 세로일때 어떻게 구현할 것 인가 -> 빡구현이 정답인가..

💡 Solution 

0. 일단 블록이 범위를 넘어갔는지 파악하는 것을 용이하게 하기 위해서 테두리를 1로 두른다.

여기서 주의할 점은 new_board[i+1][j+1] = board[i][j] 라는 것이다. 그리고 new_board는 (n+2)*(n+2)이다.

    #외부 벽 1로 두르기 
    n = len(board)
    new_board = [[1]*(n+2) for _ in range(n+2)]
    for i in range(n):
        for j in range(n):
            new_board[i+1][j+1] = board[i][j]

 

1. visited 처리: 와 여기서 놀랐던것이 있다 바로 집합 리스트로 처리하고 in 으로 방문여부를 확인할 수 있다.

#초기화
visited = [{(1,1),(1,2)}]

#방문 여부 확인
if pos not in visited:
                visited.append(pos)
                q.append((pos,time+1))

 

2. 이문제는 BFS문제 였다. DFS로 풀려면 풀 수는 있겠으나 꽤 복잡했을 것 같다. 

이문제가 BFS라는 힌트는 1) 시작점이 명확하다 2) 끝나는 점도 명확하다 3) 최단시간(거리)를 계산해라

였다.

 

3.가로일때 세로일때 어떻게 나눠서 하는가도 이문제의 관건이었는데 정답은 가로, 세로일때를 나눠주고 아래처럼 for i in [-1,1]를 사용하여 위, 아래일 경우를 계산할 수 있다는 것이다. 그리고 위칸, 아래칸이 있을때를 먼저 확인해준다(나는 한칸만 비면 되는 줄 알았는데 그게 아니라 전체 두칸 모두 비어있어야했다) 만약 두 칸 다 비어 있다면 리스트에 담아준다.

    #회전        
    #가로 방향이면
    if(r_1 == r_2):
        for i in [-1,1]:
            # 위칸 혹은 아래칸이 비어있어야함
            if(new_board[r_1+i][c_1]==0 and new_board[r_2+i][c_2]==0):
                next_pos_list.append({(r_1,c_1),(r_1+i,c_1)})
                next_pos_list.append({(r_2,c_2),(r_2+i,c_2)})
        return next_pos_list

 

전체 코드

from collections import deque
def next_position(cur,new_board):
    next_pos_list = []
    cur = list(cur)
    r_1,c_1,r_2,c_2 = cur[0][0],cur[0][1],cur[1][0],cur[1][1]
    
    dr = [0,1,0,-1]
    dc = [1,0,-1,0]
    #이동 - 공통
    for d in range(4):
        nr_1 = r_1 + dr[d]
        nc_1 = c_1 + dc[d]
        nr_2 = r_2 + dr[d]
        nc_2 = c_2 + dc[d]
        if(new_board[nr_1][nc_1]==0 and new_board[nr_2][nc_2]==0):
            next_pos_list.append({(nr_1,nc_1),(nr_2,nc_2)})
    #회전        
    #가로 방향이면
    if(r_1 == r_2):
        for i in [-1,1]:
            # 위칸 혹은 아래칸이 비어있어야함
            if(new_board[r_1+i][c_1]==0 and new_board[r_2+i][c_2]==0):
                next_pos_list.append({(r_1,c_1),(r_1+i,c_1)})
                next_pos_list.append({(r_2,c_2),(r_2+i,c_2)})
        return next_pos_list
    #세로 방향이면
    for i in [-1,1]:
        # 위칸 혹은 아래칸이 비어있어야함
        if(new_board[r_1][c_1+i]==0 and new_board[r_2][c_2+i]==0):
            next_pos_list.append({(r_1,c_1),(r_1,c_1+i)})
            next_pos_list.append({(r_2,c_2),(r_2,c_2+i)})      
    return next_pos_list


def solution(board):

    #외부 벽 1로 두르기 
    n = len(board)
    new_board = [[1]*(n+2) for _ in range(n+2)]
    for i in range(n):
        for j in range(n):
            new_board[i+1][j+1] = board[i][j]
    #bfs 
    q = deque([({(1,1),(1,2)},0)])
    visited = [{(1,1),(1,2)}]
    while q:
        cur,time= q.popleft()
        for pos in next_position(cur,new_board):
            if (n,n) in pos:
                return time+1
            if pos not in visited:
                visited.append(pos)
                q.append((pos,time+1))

    return 0