[DFS/BFS/완전탐색] ★★ 16930번 - 달리기(BFS)

[백준] 16930번 - 달리기

풀이 시간: 3시간 이내

아이디어를 떠올리고 코드를 짜는데는 30분 밖에 안걸렸지만 시간 초과를 고치는데 시간이 좀 걸린 문제다. 지금까지 내가 겪었던 시간 초과 문제들에서 보통은 몇가지 방법들을 쓰면 해결이 되었는데 이 문제는 설계를 꼼꼼하게 하지 못해 일어난 시간초과 문제로 해결하기가 힘들었다. 꼭 복습이 필요한 문제!!

 

매 초마다 상하좌우 중 1가지 방향으로 이동할 수 있고 최소 1개~최대 K개의 빈칸을 이동할 수 있다.

시작점에서 도착점까지 이동하는 최소 시간을 구하는 문제로 BFS로 풀 수 있는 문제이다.

일반적인 BFS 문제는 상하좌우로 한 칸씩만 이동할 수 있으나 이 문제는 상하좌우로 (1~K)칸의 연속된 빈칸을 이동할 수 있다는 것이 중요 포인트다.

(풀이1) 시간초과 코드

1) 문제 해결 아이디어

첫번째 오류. 시간 초과

1. input() 대신에 sys.stdin.readline() 쓰기

2. 처음엔 dx, dy 위치 벡터를 써서 for문을 돌린 것 때문인가 싶어서 for문을 if문 4번으로 고쳤는데 96%까지 잘되다가 시간초과가 떠서 실패했다.

3. 끝점인지 검사하고 종료하는 코드의 위치가 문제인가 싶어서 큐에 삽입할때 끝점이면 바로 종료하게 했는데 여전히 96%까지 잘되다가 시간초과가 떠서 실패했다.

 

2) 소스코드

from collections import deque
import sys
input = sys.stdin.readline()

# BFS
def bfs(x1, y1, x2, y2):
  queue = deque()
  # 시작점 삽입, 방문 처리
  queue.append((x1, y1))
  graph[x1][y1] = 0

  while queue:
    x, y = queue.popleft()
    # 끝점에 도착했으면 종료
    if(x == x2 and y == y2):
      return graph[x2][y2]
    # 상하좌우 탐색
    for i in range(4):
      for j in range(1, k + 1):
        nx = x + dx[i] * j
        ny = y + dy[i] * j
        # 범위 내이고
        if(0 <= nx < n and 0 <= ny < m):
          # 방문하지 않은 빈칸이면
          if(graph[nx][ny] == '.'):
            # 삽입, 방문 처리
            queue.append((nx, ny))
            graph[nx][ny] = graph[x][y] + 1
          elif(graph[nx][ny] == '#'):
            break
        else: break
  return -1

n, m, k = map(int, input().split())  # 세로, 가로, 1초에 이동가능한 최대 칸
# n * m (.: 빈칸 #: 벽)
graph = [list(input()) for _ in range(n)]
x1, y1, x2, y2 = map(int, input().split())  # 시작점, 끝점
visited = [[0] * m for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

print(bfs(x1-1, y1-1, x2-1, y2-1))

 

(풀이2) 정답 코드

1) 문제 해결 아이디어

내가 간과한 점은 상하좌우로 (1~K)칸의 연속된 빈칸을 이동할 수 있다는 조건때문에 탐색방향순서가 어떻게 설정되는지에 따라 결과값이 달라질 수 있다는 점이다...

정말 생각지도 못한 부분이라 정답 코드를 보고도 이해가 가지 않았는데 아래 글을 보고서야 이해가 됐다..

여기서 중요 포인트는 방문했던 길의 경우 무조건 방문하지 않게 하면 문제가 생기므로 적절한 조치를 취해야 한다는 것이다. 아래의 4-1 조건을 생각해내는게 정말 어려운 것 같다. 풀이를 보지 않았으면 절대 생각해내지 못했을 것이다....

 

예를 들어 아래와 같은 상황이 주어진다고 하자.

1. 아래쪽->오른쪽 순서로 탐색한다고 하면 시작지점에서 끝지점까지의 최소 시간은 2가 된다.

 

2. 하지만 오른쪽->아래쪽 순서로 탐색한다면 실제 시작지점에서 끝지점까지의 최소 시간은 2가 되어야 하지만 아래와 같이 최소 시간은 3이 되는 문제가 발생한다.

3. 이를 해결하기 위한 방법은 방문한 길의 값이 현재값보다 크다면 방문한 길을 건너 뛰고 다음 길을 또 탐색하게 하는 것이다. 아래와 같이 0열에 있는 1들은 원래라면 오른쪽이 방문한 길(2)이므로 더이상 탐색을 진행할 수 없지만 현재값(1)보다 방문한 길(2)가 더 크기 때문에 2를 건너뛸 수 있게 된다. (빨간색 2는 파란색 2를 건너뛰어 탐색한 값이다.)

<탐색할 좌표 경우의 수>

1. 범위 밖을 벗어남 → break(다음 방향 탐색)

2. 벽 → break(다음 방향 탐색)

3. 방문하지 않은 길 → 큐에 삽입, 방문처리

4. 방문했던 길

4-1. 기준 값보다 방문했던 길의 값이 큼 → break하지 않고 이어서 다음 칸 탐색

4-2. 기준 값보다 방문했던 길의 값이 같거나 작음 → break(다음 방향 탐색)

 

[참고] https://velog.io/@redcarrot01/ProblemSolving-%EB%B0%B1%EC%A4%80-16930-%EB%8B%AC%EB%A6%AC%EA%B8%B0dfsbfs

[ProblemSolving] 백준 - 16930 달리기(dfs&bfs)

[참고] https://salepark.tistory.com/88

[백준] 16930 달리기

 

2) 소스코드

from collections import deque
import sys
input = sys.stdin.readline

# BFS
def bfs(x1, y1, x2, y2):
  queue = deque()
  # 시작점 삽입, 방문 처리
  queue.append((x1, y1))
  graph[x1][y1] = 0

  while queue:
    x, y = queue.popleft()
    # 끝점에 도착했으면 종료
    if(x == x2 and y == y2):
      return graph[x2][y2]
    # 상하좌우 탐색
    for i in range(4):
      for j in range(1, k + 1):
        nx = x + dx[i] * j
        ny = y + dy[i] * j
        # 범위 밖이면 다음 방향 탐색
        if(nx < 0 or nx >= n or ny < 0 or ny >= m): break
        # 벽이면 다음 방향 탐색
        if(graph[nx][ny] == '#'): break
        # 방문하지 않은 길이면 큐에 삽입, 방문 처리
        if(graph[nx][ny] == '.'): 
            queue.append((nx, ny))
            graph[nx][ny] = graph[x][y] + 1
        # 방문한 길인데 기준값보다 더 크다면 break하지 않고 다음 칸 이어서 탐색
        elif (graph[nx][ny] > graph[x][y]): continue
        else: break
  return -1

n, m, k = map(int, input().split())  # 세로, 가로, 1초에 이동가능한 최대 칸
# n * m (.: 빈칸 #: 벽)
graph = [list(input()) for _ in range(n)]
x1, y1, x2, y2 = map(int, input().split())  # 시작점, 끝점
visited = [[0] * m for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

print(bfs(x1-1, y1-1, x2-1, y2-1))