파이썬 알고리즘 181번 | [백준 2589번] 보물섬 - BFS

181. 보물섬

주의할 점 : 처음 출발 지점은 세지 않음

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

• BFS !! 이제 두번 활용하니깐 확 복습 쫙 되네
• BFS 는 큐를 활용하고 방문 여부 체크 필요, 거리 계산할거라서 DIS라는 리스트 만들면 사실 상 얘가 방문 여부 체크 역할도 하기에 (방문 안된 것은 거리가 0 일테니) 방문 리스트 안 만들어도 되긴 함 ㅇㅇ

2) 코딩 설명

• LAND 인 친구들을 골라서 리스트에 담아주고,
• LAND 안에 든 아이들을 시작점으로 삼아서, 걔를 시작으로 다른 land 이면서 체크 안된 아이들 까지의 최단 거리들을 dis 라는 이차원 배열에 기록해 줌
• 한 시작점 도는 것 끝날 때마다, dis 배열 가져와서 그 dis 에서 가장 긴 거리의 값아이를 target 이랑 비교한 후, 둘 중에 더 큰 아이를 target 으로 갱신시켜주다보면 답이 나온다.

<내 풀이>

from collections import deque
import sys

target = -999

def bfs(q):
    while q :
        now = q.popleft() #(0,1) 의 (x,y) 형태로 빠져나옴
        #print(now)
        for i in range(4) : #상하좌우 살펴봐야 함
            tmpr = now[0]+rloc[i] # x가 column 열이고
            tmpc = now[1]+cloc[i] # y가 row 행임 , 따라서 [tmpy][tmpx] 순서 
            if 0<=tmpr<r and \
                0<=tmpc<c and \
                    chk[tmpr][tmpc]==0 and \
                        (map[tmpr][tmpc]=='L') :
                q.append((tmpr , tmpc)) # r(행), c(열) 순으로 저장 
                chk[tmpr][tmpc] = 1
                dis[tmpr][tmpc] = dis[now[0]][now[1]]+1
                
# 행,열 값 받기
r,c = map(int,sys.stdin.readline().rstrip().split())

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

# 상하좌우
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((i,j)) # y가 행, x가 열 따라서 j,i 순으로 넣어줌 

for i in land : 
    start = i 

    # 초기화 작업 
    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[0], start[1]))
    chk[start[0]][start[1]]=1
    dis[start[0]][start[1]]=0
    #print(q)
    bfs(q)

    for i in dis :
        #print("dis " , i)
        if max(i) > target : 
            target = max(i)
print(target)

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

from collections import deque
from itertools import combinations
import sys


maxnum = -9999
def bfs(q):
    global maxnum
    while q :
        now = q.popleft() #(0,1) 의 (x,y) 형태로 빠져나옴
        
        if(maxnum < dis[now[0]][now[1]]) :
            maxnum = dis[now[0]][now[1]]

        for i in range(4) : #상하좌우 살펴봐야 함
            tmpx = now[0]+x[i] # x가 column 열이고
            tmpy = now[1]+y[i] #y가 row 행임 , 따라서 [tmpy][tmpx] 순서 

            if 0<=tmpx<c and \
                0<=tmpy<r and \
                    chk[tmpy][tmpx]==0 and \
                        (map[tmpy][tmpx]=='L') :

                q.append((tmpy, tmpx))
                chk[tmpy][tmpx]== 1
                dis[tmpy][tmpx] = dis[now[0]][now[1]]+1
                map[tmpy][tmpx] = '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

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

land =[]

for i in range(r) :
    for j in range(c) : 
        if(map[i][j]=='L') :
            land.append((i,j))

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) # (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[0], start[1]))
    chk[start[0]][start[1]]=1
    dis[start[0]][start[1]]=1
    newdis = bfs(q)


print(maxnum)

• 시간초과가 뜬다. 자자 시간을 줄여보자

from collections import deque
from itertools import combinations
import sys

target = -999
def bfs(q, startx, starty, endr, endc):
    global target
    global mapp
    while q :
        now = q.popleft() #(0,1) 의 (x,y) 형태로 빠져나옴

        if target < dis[now[0]][now[1]] :
            print(startx, starty)
            print(endr, endc)
            print(now)
            for i in dis :
                print(i)
            print('\n')
            target = dis[now[0]][now[1]]

        for i in range(4) : #상하좌우 살펴봐야 함

            tmpr = now[0]+rloc[i] # x가 column 열이고
            tmpc = now[1]+cloc[i] # y가 row 행임 , 따라서 [tmpy][tmpx] 순서 

            if 0<=tmpr<r and \
                0<=tmpc<c and \
                    chk[tmpr][tmpc]==0 and \
                        (mapp[tmpr][tmpc]=='L') :

                q.append((tmpr , tmpc)) # r(행), c(열) 순으로 저장 
                chk[tmpr][tmpc]== 1
                dis[tmpr][tmpc] = dis[now[0]][now[1]]+1
                mapp[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((i,j)) # y가 행, x가 열 따라서 j,i 순으로 넣어줌 

land2 = []

mapcpy = map.copy()

# 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) - 시작점 아이 체크 

    mapp = mapcpy # map 다시 원상복귀 
    q.append((start[0], start[1]))
    chk[start[0]][start[1]]=1
    dis[start[0]][start[1]]=1
    
    newdis = bfs(q, start[0], start[1], end[0], end[1])
    
print(target)

• 아아 뭔가 ROW, COLUMN을 혼동한듯,,? 흑흑 다시 하자잉 ㅠㅠ

<반성 점>

• 처음에 너무 어렵게 접근한 내 자신이 킹 받 는 다
• 간단하게 L 인 아이들데리고 걔네를 시작점으로 해서 쫙 다 최단거리 돌려놓고, 그 중 거리 MAX 인 값 뽑으면 게임 끝이었는데, 조합을 통해 모든 경우의 수 ; (엄청난 수, ) 를 구한 후 접근하려 한 점이 약간 아쉽쓰~

<그럼에도 배운 점>

• 그래도 조합 복습하고, 내가 행열에서 틀린 줄 알고 & 시간초과 나서 행열에 대해서 삽질을 했는데, 처음에 row col 이라 지정했으면 row col로 변수명 쭉 가고 , 그게 아니라면 한가지 변수명을 고정 ㄱㄱ

• 난 처음에 row col 이랑 x , y 같이 썼더니 헷갈려서 죽는 줄 ! 갠적으로 row col 개념이 더 편안함 (선대를 수강해서 그런가,,)!!