[BOJ 26169번] 세번 이내에 사과를 먹자(Python)

📝 문제

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

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

학생이 현재 위치 (r, c)에서 세 번 이하의 이동으로
사과를 2개 이상 먹을 수 있으면 1을 출력하고, 그렇지 않으면 0을 출력하자.

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

⚙️ 출력 : 첫 번째 줄에 학생이 현재 위치 (r,  c)에서
세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을 출력하고, 먹을 수 없으면 0을 출력한다.

 

문제링크

26169번: 세 번 이내에 사과를 먹자

---

✅ 풀이

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

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

def dfs(r,c,move,cnt):
    global bool

    cnt = cnt
    if r > 4 or c > 4 or r < 0 or c < 0 or move > 3:
        return

    if board[r][c] == -1:
        return

    if board[r][c] == 1:
        cnt += 1

    temp = board[r][c]
    board[r][c] = -1

    if cnt == 2:
        bool = True
        return

    dfs(r+1, c, move+1, cnt)
    dfs(r-1, c, move+1, cnt)
    dfs(r, c+1, move+1, cnt)
    dfs(r, c-1, move+1, cnt)

    board[r][c] = temp

dfs(r,c,0,0)
if bool:
    print(1)
else:
    print(0)

💡 backtracking의 중요성을 깨닫게 된 문제이다.
먼저 재귀적으로 탐색하며, 보드판을 넘어가거나 3회 초과로 이동했을 경우 멈췄다.
또한 방문한 장소에 장애물이 있을 경우에도 재귀를 멈췄다.
만약 방문한 장소에 사과가 있다면 cnt에 1을 더해주었고,
방문한 장소에 장애물을 두기 위해서 -1로 값을 바꿔주었다.

여기서 문제가 발생하는데,
만약 원래 방문한 장소의 값을 저장해두고 나중에 복원해주는 작업을 하지 않으면,
나중에 재귀에 의해 같은 장소를 방문했을 경우 바뀐 값으로 체크가 되기 때문이다.

따라서 해당 작업을 추가해준 다음,
사과를 2개 먹는 순간 불필요하게 추가적인 재귀를 하지 않도록
bool을 True로 바꾸고 재귀를 멈췄다.

모든 조건을 설정한 다음엔 상, 하, 좌, 우 방향으로 이동하며 재귀를 진행하도록 했다.