파이썬 알고리즘 180번 | [백준 2178번] 미로탐색- BFS

Yunny.Log ·2022년 6월 21일

Algorithm

목록 보기

183/318

180. 미로탐색

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>


from collections import deque
import sys

n,m = map(int, sys.stdin.readline().rstrip().split())
dis=[[0]*m for _ in range(n)]
q = deque()

map=[]
for i in range(n) : 
        map.append(list(sys.stdin.readline().rstrip()))

q.append((0,0))
map[0][0] = 1 # 방문완료
dis[0][0] = 1 # 얘의 거리는 1

x=[0,0,-1,1] # 상하좌우 
y=[1,-1, 0,0]

while q :
    now = q.popleft()
    for i in range(4) : #하나가 나오면 무조건 네방향 탐색 진행
        tmpx = now[0] + x[i]
        tmpy = now[1] + y[i]

        if 0<=tmpx<=(n-1) and 0<=tmpy<=(m-1) and (map[tmpx][tmpy]=='1'):
            map[tmpx][tmpy] = 0
            dis[tmpx][tmpy] = dis[now[0]][now[1]]+1
            q.append(((tmpx,tmpy)))


if (map[n-1][m-1]==0) : # 간 곳이라면 
    print(dis[n-1][m-1])

<내 틀렸던 풀이, 문제점>

내가 map 에 문자열로 '1' 을 넣고 있어서 1을 인식하지 못했어서 오류 및 오답이 발생했었다.
그래서 map[tmpx][tmpy] 를 프린트하면 1 이라고 찍히는데 map[tmpx][tmpy]==1 이라고 하면 False라고 떠서 뭐지,,하고 헤맸었다.


from collections import deque
import sys

n,m = map(int, sys.stdin.readline().rstrip().split())
dis=[[0]*m for _ in range(n)]
q = deque()

map=[]
for i in range(n) : 
        map.append(list(sys.stdin.readline().rstrip()))

q.append((0,0))
map[0][0] = 1 # 방문완료
dis[0][0] = 1 # 얘의 거리는 1

x=[0,0,-1,1] # 상하좌우 
y=[1,-1, 0,0]

while q :
    now = q.popleft()
    for i in range(4) : #하나가 나오면 무조건 네방향 탐색 진행
        tmpx = now[0] + x[i]
        tmpy = now[1] + y[i]

        if 0<=tmpx<=(n-1) and 0<=tmpy<=(m-1) and (map[tmpx][tmpy]==1):
            map[tmpx][tmpy] = 0
            dis[tmpx][tmpy] = dis[now[0]][now[1]]+1
            q.append(((tmpx,tmpy)))


if (map[n-1][m-1]==0) : # 간 곳이라면 
    print(dis[n-1][m-1])

from collections import deque
from itertools import combinations
import sys

target = -999

def bfs(q, endr, endc):
    global target

    while q :
        #print(target)
        #print(dis)
        
        if dis[endr][endc] != 0 :
            #print( dis[endy][endx])
            if target < dis[endr][endc] :
                target = dis[endr][endc] 
            
        now = q.popleft() #(0,1) 의 (x,y) 형태로 빠져나옴
        #print("nowwwwwwww : ", now)

        for i in range(4) : #상하좌우 살펴봐야 함
            tmpr = now[0]+rloc[i] # x가 column 열이고
            tmpc = now[1]+cloc[i] # y가 row 행임 , 따라서 [tmpy][tmpx] 순서 
            #print(tmpy, tmpx)
            if 0<=tmpr<r and \
                0<=tmpc<c and \
                    chk[tmpr][tmpc]==0 and \
                        (map[tmpr][tmpc]=='L') :

                q.append((tmpr , tmpc)) # y(행), x(열) 순으로 저장 
                chk[tmpr][tmpc]== 1
                
                #print(now[1], now[0])
                dis[tmpr][tmpc] = dis[now[0]][now[1]]+1
                map[tmpr][tmpc] = 'D' #done 표시

# 행,열 값 받기
r,c = map(int,sys.stdin.readline().rstrip().split())

# 지도 받기 
map=[]
for i in range(r) :
    map.append(list(sys.stdin.readline().rstrip()))

# L 들을 두개씩 묶은 조합을 제작
# bfs 로 두개의 최단 거리들을 구해서 리스트에 넣기
# L조합들의 최단거리 모음 중 가장 큰 아이 pick

# 상하좌우
rloc = [0,0,-1,1]
cloc = [1,-1,0,0]

land =[]

for i in range(r) :
    for j in range(c) : 
        if(map[i][j]=='L') :
            land.append((r,c)) # y가 행, x가 열 따라서 j,i 순으로 넣어줌 

land2 = []

# list(combinations(land,2)) : ((0, 1), (0, 2)), ((0, 1), (0, 6)), ((0, 1), (1, 0))
for i in list(combinations(land,2)) :
    start = i[0] 
    #print("start :  ", start) # (0, 1)
    end = i[1]
    # 초기화 작업 
    q=deque() #하나 popleft 되면 인접노드 담고,, 반복할 아이
    chk = [[0] * (c+1) for _ in range(r+1)] #방문 여부 체크
    dis = [[0] * (c+1) for _ in range(r+1)] #거리 정보 체크

    # 초기화 작업 (2) - 시작점 아이 체크 
    q.append((start[1], start[0]))
    chk[start[0]][start[1]]=1
    dis[start[0]][start[1]]=1

    newdis = bfs(q, end[0], end[1])
    print(target)

print(target)