백준 26169 세 번 이내에 사과를 먹자 파이썬 풀이

난이도 : 실버3

풀이일 : 11223

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

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

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

오답 코드

import sys

board = [list(map(int, sys.stdin.readline().split())) for _ in range(5)]
x, y = list(map(int, sys.stdin.readline().split()))

di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
flag = False
visited = [[False] * 5 for _ in range(5)]

def DFS(i, j, depth, apple):
    global flag
    visited[i][j] = True
    if board[i][j] == 1:
        apple += 1
    if apple == 2:
        flag = True
        return
    if depth > 2:
        return
    for k in range(4):
        ni, nj = i + di[k], j + dj[k]
        if 0 <= ni < 5 and 0 <= nj < 5:
            if board[ni][nj] != -1 and not visited[ni][nj]:
                DFS(ni, nj, depth + 1, apple)

    return

DFS(x, y, 0, 0)

if flag:
    print(1)
else:
    print(0)

• 한 번 방문했던 곳에 대해 visited 초기화 작업을 해주지 않아 문제 발생
• 아래는 이 코드로 틀렸던 반례
• 0 1 1 0 0
  0 0 0 0 0
  0 0 0 0 0
  0 0 0 0 0
  0 0 0 0 0
  0 0

---

풀이코드

import sys

board = [list(map(int, sys.stdin.readline().split())) for _ in range(5)]
x, y = list(map(int, sys.stdin.readline().split()))

di, dj = [-1, 1, 0, 0], [0, 0, -1, 1]
flag = False
visited = [[False] * 5 for _ in range(5)]

def DFS(i, j, depth, apple):
    global flag
    visited[i][j] = True
    if board[i][j] == 1:
        apple += 1
    if apple == 2:
        flag = True
        return
    if depth > 2:
        return
    for k in range(4):
        ni, nj = i + di[k], j + dj[k]
        if 0 <= ni < 5 and 0 <= nj < 5:
            if board[ni][nj] != -1 and not visited[ni][nj]:
                DFS(ni, nj, depth + 1, apple)
                visited[ni][nj] = False

DFS(x, y, 0, 0)

if flag:
    print(1)
else:
    print(0)

• DFS로 깊이 세 번 이내에 사과를 두 번 먹는 경우가 있는지 탐색
• 사과를 두 번 먹는 경우를 찾으면, flag를 True로 변경
• 최종 출력은 flag로 판단

---

느낀점

• 진짜 오랜만에 푸니까 인풋 받는 데에도 너무 오래 걸렸다.
• 이제 마지막 프로젝트가 끝났으니 매일매일 알고리즘 풀어야지.
• 같은 문제를 자바로도 풀어보면서 감 익혀야겠다.