[알고리즘 문제] BOJ 26169:세 번 이내에 사과를 먹자

DFS를 사용하여 푸는 문제입니다.

https://devbob.tistory.com/2

[알고리즘] DFS

문제

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

 

제한

• 0 ≤ r, c ≤ 4
• 현재 위치 (r, c)는 빈칸이다.

 

예제 입력 1

0 0 1 0 0
0 0 -1 0 0
0 0 1 0 0
1 1 -1 1 0
0 0 0 -1 0
4 1

 

예제 출력 1

1

 

문제 이해 및 풀이설계

1. 5*5 matrix를 만들어야 한다.

2. matrix 값을 받아야 한다.

3. 사과 먹은 갯수를 기준으로 조건문을 만들어 출력값을 결정해야한다.

4. DFS를 활용한다

-장애물이 있는 곳은 visited 처리를 하여 방문하지 않도록 한다.

-count값을 dfs 매개변수로 넣어 3이 넘어가면 출력값을 내보내도록 한다.

-사과를 먹은 최댓값을 생각하여 출력값을 결정하기로 했다. 그러므로 dfs의 결과가 apple_max값보다 큰 지를 비교해서 다시 초기화 해야한다.

 

+참고로 저는 조건중에 (r,c)가 빈칸이라는 조건을 보지 못하고 풀어서 그 경우도 나누어져 있습니다. 코드를 읽으실 때 참고해주세요.

 

def dfs(x,y,count,apple,visited):
    global apple_max
    directions=[(-1,0),(1,0),(0,-1),(0,1)]
    visited[x][y]=True

    if count==3:
        if apple>apple_max:
            apple_max=apple
        return apple_max
    
    for dx,dy in directions:
        nx,ny=x+dx,y+dy     #방향 새로 설정
        if 0<=nx<5 and 0<=ny<5 and visited[nx][ny]==False:
            visited[nx][ny]=True
            if matrix[nx][ny]==1:#사과가 있다면
                dfs(nx,ny,count+1,apple+1,visited)
            else:               #사과가 없다면
                dfs(nx,ny,count+1,apple,visited)
            visited[nx][ny]=False	#만약 다시 방문처리를 하지 않는다면 다음 반복문 상황에서 방문하지 못함
            
        
    
#행렬 생성
matrix=[]
#띄어쓰기 단위로 문자열을 끊어서 리스트에 넣고 matrix에 append
for i in range(5):
    row=list(map(int,input().split()))
    matrix.append(row)
#방문처리
visited=[[False]*5 for _ in range(5)]

for i in range(5):
    for j in range(5):
        if(matrix[i][j]==-1):
            visited[i][j]=True

#좌표값 받기
x,y=map(int,input().split(' '))           
            
#사과 max값
apple_max=0          
#처음부터 사과가 있다면 
if matrix[x][y]==1:
    dfs(x,y,0,1,visited)
#사과가 없다면
else:
    dfs(x,y,0,0,visited)




if (apple_max>=2):
    print(1)
else:
    print(0)