감옥

BFS

• 다익스트라 알고리즘으로 풀 수있고, bfs로도 풀 수 있다고 한다. 이 문제는 처음보면 정말 쪼리지만, bfs의 기초만 알고 있으면 문제 접근이 가능하다고 본다.

• 다음은 문제풀이 방법이다

  • 범죄자의 위치를 파악한다.
  • 범죄자의 위치에서 bfs를 하는데, 만약 가는 경로중에 문(#)이 있으면, 문의 갯수를 카운트하고, 이때 문을 열었으니, 다른 문자로 바꾸어 주어야한다.
  • 내가 문제가 생긴이유는 문을 열고, 문을 다른 문자로 안바꾸어주어 문제가 생긴것 같다.

  from collections import deque
  
  answer = []
  
  def my_input():
     graph = []
     height, width = map(int, input().split())
     for _ in range(height):
         graph.append(input())
     return graph, width, height
  
  def bfs(graph, i, j, queue, visited, cnt):
     global answer 
  
     dx = [-1, 1, 0, 0]
     dy = [0, 0, -1, 1]
  
     n = len(graph)
     m = len(graph[0])
  
     while queue:
         v = queue.popleft()
         for i in range(4):
             nx = v[0] + dx[i]
             ny = v[1] + dy[i]
             # 확인할 네모칸이 범위 밖이면 무시
             if nx < 0 or nx >= n or ny < 0 or ny >= m :
                 continue
             # 탈출 조건
             if (nx == 0 and graph[nx][ny] != '*') or (ny == 0 and graph[nx][ny] != '*') or (nx == n - 1 and graph[nx][ny] != '*') or (ny == m - 1 and graph[nx][ny] != '*'):
                 answer.append(cnt)
                 return cnt
             # 이미 네모칸을 방문했다면 무시
             if visited[nx][ny] == 1 or graph[nx][ny] == '*':
                 continue
             if graph[nx][ny] != '*':
                 if graph[nx][ny] == '#':
                     graph[nx][ny] == '.'
                     cnt += 1
                 queue.append([nx, ny])
                 visited[nx][ny] = 1
     return 
  
  def solution(graph, width, height):
     global cnt
     # 그래프의 각 좌표에 마킹할 필요는 없겠지? 왜냐하면, 인덱스두개로도 테두리줄에 있는지 인지가 가능하니까 
     visited = [[0] * width for _ in range(height)]
     # 탈옥자1의 위치에서 탈옥을 시전해보자 bfs를 해서 테두리에 도착하면 탈옥하는걸로 하자 
     cnt = 0
     for i in range(height):
         for j in range(width):
             if graph[i][j] == '$':
                 queue = deque()
                 queue.append([i, j])
                 if visited[i][j] == 0:
                     visited[i][j] = 1
                     bfs(graph, i, j, queue, visited, cnt)
     pass
  
  def main():
     global answer
     graph, width, height = my_input()
     solution(graph, width, height)
     print(answer)
     print(graph)
  
  main()
  

• 뭔가 꺼림칙한게 열어야하는 최소의 문이라고 하니까… 흠.. 어렵다..
• 어떻게 최소의 문을 구하지?…… 내 생각은 모든경로중에서 탈출할수있는 경로들 구하고 그 경로들 중에서 문이 가장 작게 열리는거 찾으면돌ㄷ스