(Python/LV2) 미로탈출

문제출처:https://school.programmers.co.kr/learn/courses/30/lessons/159993

프로그래머스

풀이:

from collections import deque
def solution(maps):

    board = [list(maps[i]) for i in range(len(maps))]


    f_n, f_m = 0, 0
    s_n, s_m = 0, 0
    Q = deque([])

    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == "S":
                board[i][j] = 0
                Q.append((i,j))
            if board[i][j] == 'L':
                f_n = i
                f_m = j
            if board[i][j] == "E":
                s_n = i
                s_m = j
    x = bfs(Q,f_n,f_m,board)
    board[f_n][f_m] = x
    Q.append((f_n,f_m))
    y = bfs(Q,s_n,s_m,board)
    if x != -1 and y != -1:
        return y
    else:
        return -1
def bfs(Q,start,end,board):
    # print(Q,start,end,board)
    move = [(-1,0),(1,0),(0,1),(0,-1)]
    while Q:
        x, y = Q.popleft()
        for a, b in move:
            nx, ny = x+a, y+b
            if nx == start and ny == end:
                return board[x][y] + 1
            if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] =="O":
                board[nx][ny] = board[x][y] + 1
                Q.append((nx,ny))
    return -1


print(solution(["SOOOL", "XXXXO", "OOOOO", "OXXXX", "OOOOE"]))
# print(solution(["LOOXS", "OOOOX", "OOOOO", "OOOOO", "EOOOO"]))

30점 받는 bfs 풀이 bfs 를 두번 돌려야한다.

 

visited 를 만들어서 시도해봄 

from collections import deque
def solution(maps):

    def bfs(start,end,start2,end2):
        move = [(-1,0),(1,0),(0,1),(0,-1)]
        visited = [[-1]*len(maps[0]) for _ in range(len(maps))]
        visited[start][end] = 0
        Q = deque([(start,end)])
        while Q:
            x, y = Q.popleft()
            if x == start2 and y == end2:
                return visited[start2][end2]
            for a, b in move:
                nx, ny = x+a, y+b
                if 0 <= nx < len(maps[0]) and 0 <= ny < len(maps)  and visited[nx][ny] == -1 and maps[nx][ny] != 'X':
                    visited[nx][ny] = visited[x][y] + 1
                    Q.append((nx,ny))
        return -1

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == "S":
                S = (i,j)
            if maps[i][j] == 'L':
                L = (i,j)
            if maps[i][j] == "E":
                E = (i,j)

    answer2 = bfs(S[0],S[1],L[0],L[1])
    answer3 = bfs(L[0],L[1],E[0],E[1])
    
    if answer2 != -1 and answer3 != -1:
        return answer2 + answer3
    else:return -1



print(solution(["SOOOL", "XXXXO", "OOOOO", "OXXXX", "OOOOE"]))
# print(solution(["LOOXS", "OOOOX", "OOOOO", "OOOOO", "EOOOO"]))

65점 틀린것들은 런타임에러들,

 

 

고민 좀 많이 했는데 가로세로 이슈 였다 

if 0 <= nx < len(maps) and 0 <= ny < len(maps[0])  and visited[nx][ny] == -1 and maps[nx][ny] != 'X':

maps[0] 과 len(maps)를 바꿔줌

 

bfs 마스터했다 생각했지만 2개 물어보니 바로 뇌가 잠깐 꼬임