백준 26170 : 사과 빨리 먹기(Python 파이썬)

 

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

 

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을 출력한다.

 

문제 접근

백준 26169와 굉장히 유사한 문제이다. 차이가 있다면 사과 3개를 먹기 위한 최소 이동 횟수를 출력해야 하는 부분이다. 26169에서는 사과의 수를 이차원 리스트로 만들어서 dfs에 인자로 전달하면서 계산을 진행해 주었지만, 이번 문제에서는 그럴 필요가 없었고, 그렇게 해서는 안되었다. 단순한 경로 탐색과 유사하다고 생각하고 dfs로 문제에 접근하자는 생각을 해보았다.

코드 

import sys

def dfs(road, x, y,count,apple,answer):
    if apple == 3:
        answer.append(count)
    dx = [0,-1,0,1]
    dy = [-1,0,1,0]
    for i in range(4):	#4개의 방향으로 돈다
        ddx = x + dx[i]
        ddy = y + dy[i]
        if ddx < 0 or ddx > 4 or ddy < 0 or ddy > 4: #범위가 아니라면 pass
            continue
        if road[ddx][ddy] == -1:	#해당 좌표가 -1 이라면 막혔으니 pass
            continue
        if road[ddx][ddy] == 1:	#1이라면 status를 True로 정해주고 apple의 수를 증가한다.
            status = True
            apple+=1
        else:
            status = False	#0일 경우에는 status를 False로 한다. 
        cnt = road[x][y]	#dfs에서 빠져 나왔을 경우 road[x][y]의 값을 복귀시켜야 하기 때문에 변수에 저장시켜 놓는다.
        road[x][y] = -1
        dfs(road, ddx,ddy,count+1, apple,answer)
        road[x][y] = cnt	#빠져나왔을 경우 좌표 값 원복
        if status == True:	#만약 사과를 하나 챙겼다면 원복
            apple -=1
    return answer
road = []
for i in range(5):
    a = list(map(int, sys.stdin.readline().split()))
    road.append(a)
x,y = map(int, sys.stdin.readline().split())
apple = 0
answer = []
if road[x][y] == 1:
    apple +=1
answer = dfs(road,x,y,0,apple, answer)
if len(answer) == 0:
    print(-1)
else:
    print(min(answer))

 

느낀점

dfs 문제를 계속 풀다 보니 어떻게 풀어야 할지 감이 잘 온다. 하지만, 인자를 너무 많이 넘겨 버리는 것은 개발에서의 좋은 습관이 아니라고 배웠다. 이를 고쳐야 할 필요가 있을 것 같다. 뿐만 아니라, dfs를 빠져나왔을 때의 처리가 미숙하여 시간을 오래 잡아먹었다. 이 부분도 빠르게 채워나가야 할 필요가 있을 것 같다.