[백준26169] / 세 번 이내에 사과를 먹자 - DFS,백트래킹

 

백준26169

 

푼 날짜 : 2024.12.04

푼 문제 : [26169] / 세 번 이내에 사과를 먹자

사용한 언어 : python

알고리즘 : DFS, 백트래킹

 

 

접근방식 :

조건은 "세 번 이하의 이동으로 사과를 2개 이상 먹을 수 있으면 1을 출력하고, 그렇지 않으면 0을 출력"이다.

백트래킹 방식으로 풀이했다.

 

 

코드 :

import sys

input = sys.stdin.readline
NUM = 5

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

# 정답 확인을 위한 0, 1 체크용 변수
check = 0

# py, px -> 시작위치, cnt -> 사과 개수 확인, now -> 이동 횟수 확인
def backtracking(graph, visited, py, px, cnt, now):
    global check
	
    # 3번 이하의 이동이면서 2개 이상의 사과를 먹었을 때
    if cnt > 1 and now < 4: 
        check = 1
        return check 
    
    visited[py][px] = 1
    
    for i in range(4):
        ny, nx = py+dy[i], px+dx[i]
		
        if 0<=ny<NUM and 0<=nx<NUM:
            if not visited[ny][nx] and graph[ny][nx] != -1:
                visited[ny][nx] = 1
                if graph[ny][nx]: cnt += 1
                backtracking(graph, visited, ny, nx, cnt, now+1) # 이동 횟수 증가
                if graph[ny][nx]: cnt -= 1
                visited[ny][nx] = 0
	
    return check

graph = []
for _ in range(NUM):
    lst = list(map(int, input().split()))
    graph.append(lst)

R, C = map(int, input().split())

visited = [[0 for _ in range(NUM)] for _ in range(NUM)]
ans = backtracking(graph, visited, R, C, 0, 0)
print(ans)

 

 

오랜만에 포스팅이다. 

앞으로도 자주 올릴 수 있도록 열심히 해야지!!