백준 16432번: 떡장수와 호랑이 (Python/Java)

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

16432번: 떡장수와 호랑이

 

 

 

접근

---

구현 방법만 잘 파악하고 있다면 어렵지 않게 풀 수 있는 문제. 우선 오늘 받은 떡의 종류를 차례로 배열에 넣어준다. 이렇게 모은 각 날짜의 떡 종류 배열을 토대로 깊이 우선 탐색을 해준다. 이때, 체크해야 할 두 가지 조건이 있다. 첫 번째는 당연하게도 현재 날짜의 현재 떡에 접근한 적 있는지 탐색 여부다. 탐색 여부를 체크하지 않고 중복 방문을 허용한다면 연산이 기하급수적으로 늘어날 것이다. 두 번째로 체크해야 할 조건은 문제에서 나왔 듯, 전날 떡과 오늘 떡의 동일 여부다. 어제 떡과 오늘 떡이 같으면 해당 떡에 접근할 수 없다. 이 두 가지를 주의한다면 어렵지 않게 문제를 해결할 수 있다.

 

해당 문제는 루트 노드에서 끝까지 갈 수 있는지, 없는지를 확인하는 문제이기 때문에 깊이 우선 탐색을 통해서 풀어주는 것이 가장 좋은 방법이다. 백트래킹을 통해 구현한다면 예제는 나올 것이다. 하지만 주어지는 조건의 범위가 넓어진다면 시간 초과가 나기 때문에 주의해야 한다.

 

 

 

풀이

---

Python

import sys
sys.setrecursionlimit(10**6)

def dfs(today, yesterday, list):
    global visitList

    if today == dayNum:
        for i in range(dayNum):
            print(list[i])

        exit()
    
    for i in riceList[today]:
        if not visitList[today][i]:
            if i != yesterday:
                visitList[today][i] = True
                dfs((today+1), i, (list + [i]))

dayNum = int(input())

riceList = []
visitList = [[False for i in range(10)] for i in range(dayNum)]
for i in range(dayNum):
    firstLine = (input()).split()

    riceNum = int(firstLine[0])
    subList = []
    for j in range(1, riceNum+1):
        subList.append(int(firstLine[j]))
    
    riceList.append(subList)

dfs(0, 0, [])

print(-1)

 

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int dayNum;
    static ArrayList<int[]> riceList = new ArrayList<int[]>();
    static boolean[][] visitList;

    public static void main(String[] args) throws IOException{
        
        dayNum = Integer.parseInt(br.readLine());

        visitList = new boolean[dayNum][10];
        for(int i = 0 ; i < dayNum ; i++){
            String[] firstLine = (br.readLine()).split(" ");

            int riceNum = Integer.parseInt(firstLine[0]);
            int[] subList = new int[riceNum];
            for(int j = 1 ; j < (riceNum+1) ; j++){
                subList[j-1] = Integer.parseInt(firstLine[j]);
            }

            riceList.add(subList);
        }

        dfs(0, 0, new int[dayNum]);

        bw.write("-1");
        br.close();
        bw.flush();
        bw.close();

    }

    private static void dfs(int today, int yesterday, int[] list) throws IOException{

        if(today == dayNum){
            for(int i = 0 ; i < dayNum ; i++){
                bw.write(list[i] + "\n");
            }

            br.close();
            bw.flush();
            bw.close();

            System.exit(0);
        }

        for(int i : riceList.get(today)){
            if(!visitList[today][i]){
                if(i != yesterday){
                    visitList[today][i] = true;
                    list[today] = i;
                    dfs((today+1), i, list);
                }
            }
        }
    }

}

 

 

 

후기

---

어려운 문제가 아니었음에도 불구하고 이상할 정도로 오답이 많이 나왔던 문제. 차근차근 문제점을 찾아보니 dfs를 할 때 떡 목록을 정리해주는 과정에서 오류가 크게 있었다. 오랜만에 풀어보는 깊이우선탐색 문제라 '그 사이 개념이 취약해졌나?'하고 생각하고 그 부분만 집중적으로 보고 있었는데 dfs를 활용하는 부분이 아니라 배열을 수정하는 부분에 문제가 있어 조금 허탈했다. 푼 문제가 오답인 경우 내가 생각한 부분뿐만 아니라 전체적으로 꼼꼼하게 살펴보는 습관을 들이도록 노력해야겠다.