[Python][백준 23817][BFS, DFS, BruteForce] 포항항 - 컴도리돌이

23817번: 포항항

---

풀이과정

후,, 기나긴 싸움

해당 문제를 해결하려고 많은 시행착오가 있었습니다. 😂

 

맞왜틀.. python3로는 해결할 수 없는 건가..

실력이 부족하여 해결하지는 못했지만

혹시 해결하신 분 있으시면 댓글로 달아 주시면 감사하겠습니다.

😊

 

1. 해당 문제는 dfs, bfs 둘 다 사용하였다.

 

2. 데이터를 입력받을 때 "S"와 "K"의 좌표를 미리 dist 배열에 튜플 형식으로 입력받았다.

입력받을 때는 "S"에서 시작하기 때문에 dist 배열의 0번째 인덱스로 두었다.

나머지 "K"가 입력받을 때는 append를 사용해서 배열에 삽입을 하였다.

 

3. BFS

bfs의 활용은 2번에서 "S"와 "K"의 좌표들을 입력받았다.

각각의 좌표에서 다른 좌표까지 거리를 입력받기 위해 사용된다.

입력받은 idx의 값의 좌표를 방문 표시하고 큐에 집어넣고

빈 큐가 될 때까지 반복문을 시행한다.(전형적인 BFS)

현재 큐의 front에서 상하좌우로 이동할 때 맵을 벗어나지 않고,

방문하지 않고,

이동한 좌표가 "X"가 아닐 때 큐에 해당 좌표를 삽입한다.

방문 표시는 이전 좌표의 이동 횟수에서 +1을 시킨다. (visited[nx][ny] = visited[x][y] + 1)

기준점이 현재 idx부터의 거리이기 때문에

 

brute 2중 배열에 현재 idx에서 다른 idx까지의 거리를 업데이트해준다.

업데이트해줄 때 해당 값이 0이면

이동할 수 없는 거리이기 때문에 INF로 업데이트해준다.

 

4.DFS

dfs 활용은 시작 인덱스부터 이동해서 5개의 "K"를 방문할 때

거리의 합이 작은 것을 업데이트하기 위해서 사용된다.

 

첫 번째 인덱스는 "S"이기 때문에 방문 표시를 미리하고 탐색을 시행한다.

다음 "K"로 이동할 때 해당 거리가 연결되어있는지 확인하고,

만약 방문하지 않은 "K" 인덱스일 경우 

방문 표시를 해주고,

깊이를 +1, 해당 이동 거리를 더해주고, 다시 탐색을 해준다.

탐색을 끝나면 방문 표시를 다시 False로 해준다.

 

깊이가 5일 경우 ans를 지금까지 이동길이와 비교해서 

작은 값을 ans에 업데이트해준다.

 

5. 

ans가 INF가 아닐 경우 해당 ans를 출력한다.

ans가 INF이면 5곳을 방문하지 못한 것이기 때문에 -1을 출력한다.

---

풀이 코드

import sys,collections
input = sys.stdin.readline

n,m = map(int,input().split())
board = []
dist = [()]
dx,dy = [0,0,-1,1],[-1,1,0,0]

## 데이터 입력 받기
for i in range(n) :
  tmp = list(input().strip())
  # 입력 받은 "S" 좌표, "K" 좌표 dist 배열에 저장
  for j in range(m) :
    if tmp[j] == "S" :
      dist[0] = (i,j)
      tmp[j] = '.'
    elif tmp[j] == "K" :
      dist.append((i,j))
      tmp[j] = '.'
  board.append(tmp)

## 각각의 S, K 의 거리 구하기 브루트 포스, BFS
def bfs(idx) :
  sx,sy = dist[idx] # 시작 좌표
  visited = [[0] * m for _ in range(n)] # 시작 좌표에서 다른 좌표까지 거리 업데이트
  visited[sx][sy] = 0
  q = collections.deque([(sx,sy)])
  while q :
    cx,cy = q.popleft()
    for i in range(4) :
      nx,ny = cx + dx[i], cy + dy[i]
      if 0<= nx < n and 0<= ny < m and not visited[nx][ny] and  board[nx][ny] != "X" :
        visited[nx][ny] = visited[cx][cy] + 1
        q.append((nx,ny))
      
  for i in range(k) :
    if i == idx : continue #현재 인덱스와 같을 경우 pass
    nx,ny = dist[i] # 다른 "K" or "S" 좌표
    # 이동 거리가 0이 아닐 경우, 그대로 반영 0일 경우 INF
    brute[idx][i] = INF if visited[nx][ny] == 0 else visited[nx][ny] 

INF = 987654321 
k = len(dist) # "S", "K" 의 좌표 개수
brute = [[INF] * (k) for _ in range(k)] # 좌표의 개수만큼 거리를 구하기 위해서
ans = 987654321
kvisited = [False] * k # dfs에서 사용할 방문 표시 배열

# "S", "K" 서로 거리 구하기 위한 bfs 
for i in range(k) :
  bfs(i)

def dfs(cur,sum,depth) :
  global ans
  # 탐색 도중에 sum이 기존 ans 보다 클 경우 return
  if ans <= sum : return
  # 깊이가 5일 때, ans값 업데이트
  if depth == 5:
    ans = min(ans,sum)
    return
  for next in range(k) :
  	# 다음 인덱스와 연결되고 방문하지 않을 경우 해당 next를 dfs 탐색
    if kvisited[next] or brute[cur][next] >= INF : continue
    kvisited[next] = True
    dfs(next,sum + brute[cur][next],depth+1)
    kvisited[next] = False
    
kvisited[0] = True
dfs(0,0,0)
print(ans if ans != INF else -1)