[Python | 백준 26170번] 사과 빨리 먹기

https://www.acmicpc.net/problem/26170

 

문제

5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자는 사과가 1개 있는 격자, 장애물이 있는 격자, 빈칸으로 되어 있는 격자로 구분된다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호를 나타낸다. 행 번호는 맨 위 위치가 0이고 아래 방향으로 1씩 증가한다. 열 번호는 맨 왼쪽 위치가 0이고 오른쪽으로 1씩 증가한다. 즉, 맨 왼쪽 위 위치가 (0, 0), 맨 아래 오른쪽 위치가 (4, 4)이다.

현재 한 명의 학생이 (r, c) 위치에 있고 한 번의 이동으로 상, 하, 좌, 우 방향 중에서 한가지 방향으로 한 칸 이동할 수 있다. 학생이 사과가 있는 칸으로 이동하면 해당 칸에 있는 사과를 1개 먹는다. 장애물이 있는 칸으로는 이동할 수 없다. 학생이 지나간 칸은 학생이 해당 칸을 떠나는 즉시 장애물이 있는 칸으로 변경된다. 즉, 학생이 해당 칸에서 상, 하, 좌, 우 방향으로 한 칸 이동하는 즉시 해당 칸은 장애물이 있는 칸으로 변경된다.

학생이 현재 위치 (r, c)에서 사과 3개를 먹기 위한 최소 이동 횟수를 출력하자. 현재 위치에서 사과 3개를 먹을 수 없는 경우 -1을 출력한다.

입력

첫 번째 줄부터 다섯 개의 줄에 걸쳐 보드의 정보가 순서대로 주어진다. i번째 줄의 j번째 수는 보드의 (i - 1)번째 행, (j - 1)번째 열의 정보를 나타낸다. 보드의 정보가 1이면 해당 칸은 사과가 1개 있는 격자임을 나타내고, 0이면 빈칸이 있는 격자를 나타내고, -1이면 장애물이 있는 격자임을 나타낸다.

다음 줄에 학생의 현재 위치 r, c가 빈칸을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄에 학생이 현재 위치에서 사과 3개를 먹기 위한 최소 이동 횟수를 출력한다. 사과 3개를 먹을 수 없는 경우 -1을 출력한다.

 

---

내 풀이

이 문제에서 가장 어려웠던 점은 사과를 3개를 먹었을 경우의 길이를 모두 구한다음에 그 중에서 최소 횟수를 구하는 방식을 구해야하다보니, 자식 노드로 한 단계 들어갈때와 나갈 때 사과의 갯수 조정, 이동 횟수 조정이 필요하다는 점이었다. 어떤 지점에 적용해야하는지 몰라서 많이 헤매다가 결국 인터넷에 다른 사람이 푼 것들을 참고해서 풀었다. 

 

#31668kb 140ms

board = []
for _ in range(5):
  board.append(list(map(int, input().split())))

r, c = map(int, input().split())

apple = move = 0
answer = []

x = [1,-1,0,0]
y = [0,0,1,-1]

def dfs(r, c, move):
  global apple
  if apple == 3:
    answer.append(move)

  for i in range(4):
    nx = r + x[i]
    ny = c + y[i]

    if (0 <= nx < 5) and (0 <= ny < 5) and (board[nx][ny] != -1):
        if board[nx][ny] == 1:
          apple += 1

        temp = board[r][c]
        board[r][c] = -1
        dfs(nx, ny, move+1)
        board[r][c] = temp

        if board[nx][ny] == 1:
          apple -= 1

  return answer

if dfs(r,c, move):
  print(min(answer))
else:
  print(-1)

 

다른 분들이 푸신것을 보니 board와 answer에 대한 정보도 같이 갱신해주면서 함수를 적용하였는데,

➡ dfs(board, r, c, move, answer) 같이 

그냥 언뜻 생각하기에 board(보드판 이동 정보)와 apple(사과 갯수)은 자식 노드와 부모 노드 간에 dfs 이동 전 후로 이미 처리해주고 있으니 굳이 같이 한 번 더 갱신해줄 필요가 없을 것 같아서 같이 갱신 안해줘봤다. 

 

answer의 경우에는 어차피 def 밖에서 정의해줬고, apple이 3개일 때만 append로 입력받기 때문에 깊이 이동간에 연관 엇없을 것 같아서 갱신을 안해보았다. 

 

다행히 백준 문제 처리에서는 따로 문제 없이 정답처리가 되었다. 

물론 테스트 케이스만 맞고 일부 논리 오류가 있을 수 있긴 할 것이다. 

 

아무튼 오랜만에 풀었더니 아직 갈길이 멀다는 사실을 한 번 더 깨달았던 문제였다. 

 

메모

dfs 문제, 실버3