[DFS/BFS/완전탐색] 17086번 - 아기 상어2(BFS)

[백준] 17086번 - 아기 상어2

풀이 시간: 40분 이내

유사 문제: 7576번

https://hseungyeon.tistory.com/217

[DFS/BFS/완전탐색] ▲ 7576번 - 토마토

N * M의 맵에서 상어 위치 기준 둘러싼 8개의 좌표로 이동이 가능하다. 

이 문제는 처음에 BFS로 풀어야 하나 싶지만 1개 이상의 상어에서 가장 멀리 떨어진 칸을 찾는 문제로 BFS로 풀어야하는 문제이다.

 

(풀이1) 시간 초과한 코드(0인 곳에서 bfs 호출)

1) 문제 해결 아이디어

처음 떠올린 방법은 for문을 돌려 빈칸(0)인 좌표에서 모두 bfs()를 호출해 얻은 리턴값들 중 최댓값을 구하는 방식이다. 

 

<동작 과정>

1. 방문 여부를 체크하는 visited를 0으로 초기화

2. 시작 지점 삽입, 방문 처리

3. 8가지 방향 탐색

3-1. 큐에서 좌표 꺼내기

3-2. 탐색할 좌표가 범위 내이고 빈칸(0)이고 방문하지 않은 칸이라면 큐에 삽입, 방문 처리

3-3. 탐색할 좌표가 상어(1)이면 visited의 이전 좌표값을 리턴(종료 조건)

 

첫번째 오류. 시간 초과

문제를 곧이 곧대로 받아들였을 때 이러한 방식으로 풀이가 가능하다. 하지만 빈칸(0)인 좌표에 대해서 매번 bfs()를 수행하기 떄문에 시간초과 문제가 생기게 된다. 

 

2) 소스코드

from collections import deque

# BFS
def bfs(x, y):
  visited = [[0] * m for _ in range(n)]
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, y))
  visited[x][y] = 1 

  while queue:
    x, y = queue.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if(0 <= nx < n and 0 <= ny < m):
        # 빈칸이고 방문한적이 없으면
        if(graph[nx][ny] == 0 and visited[nx][ny] == 0):
          queue.append((nx, ny))
          visited[nx][ny] = visited[x][y] + 1
         # 상어 좌표이면
        elif(graph[nx][ny] == 1):
          return visited[x][y]

n, m = map(int, input().split())  # 세로, 가로
# n * m (0: 빈칸, 1: 아기 상어)
graph = [list(map(int, input().split())) for _ in range(n)]
# 상하좌우 대각선
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]

safe = []
max_dis = -1
for i in range(n):
  for j in range(m):
    if(graph[i][j] == 0):
      dis = bfs(i, j)
      if(dis > max_dis):
        max_dis = dis
      #safe.append(bfs(i, j))
#print(max(safe))
print(max_dis)

 

(풀이2) 정답 코드(1인 곳에서 동시에 bfs 수행)

1) 문제 해결 아이디어

생각해보니 내가 왜 처음에 저렇게 코드를 짰나 싶었다. 

for문을 돌려 상어(1)인 좌표를 구해서 shark라는 리스트에 넣고bfs()에 상어 좌표들(sharks)을 리스트로 넘겨주면 된다. 이 문제의 포인트는 상어좌표들을 기준으로 동시에 bfs()를 수행하는 것이다.

 

<동작 과정>

1. 상어 좌표들(sharks)을 모두 큐에 삽입

2. 8가지 방향 탐색

2-1. 큐에서 좌표 꺼내기

2-2. 탐색할 좌표가 범위 내이고 빈칸(0)이고 방문하지 않은 칸이라면 큐에 삽입, 방문 처리

3. graph에서 최댓값 구하고 (최댓값 - 1) 리턴 (안전 거리는 실제 칸에 기록된 값보다 1이 작기 때문)

 

2) 소스코드

from collections import deque

# BFS
def bfs(sharks):
  queue = deque()
  # 시작 지점 삽입
  for i in range(len(sharks)):
    x, y = sharks[i][0], sharks[i][1]
    queue.append((x, y))

  while queue:
    x, y = queue.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if(0 <= nx < n and 0 <= ny < m):
        # 빈칸이고 방문한적이 없으면
        if(graph[nx][ny] == 0):
          queue.append((nx, ny))
          graph[nx][ny] = graph[x][y] + 1
  # 최댓값 계산
  max_dis = max(map(max, graph))
  return max_dis - 1

n, m = map(int, input().split())  # 세로, 가로
# n * m (0: 빈칸, 1: 아기 상어)
graph = [list(map(int, input().split())) for _ in range(n)]
# 상하좌우 대각선
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]

sharks = []  # 상어 좌표들
for i in range(n):
  for j in range(m):
    # 상어 좌표 찾기
    if(graph[i][j] == 1):
      sharks.append((i, j))
print(bfs(sharks))