[ Baekjoon - 09/18 ] - 17359번: 전구 길만 걷자

• 문제 링크 : https://www.acmicpc.net/problem/17359

17359번: 전구 길만 걷자

 

• 소요 시간 : 2시간 30분

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 512MB
   • 문제
     • 전구 묶음 개수 N(1≤N≤10)
     • 켜진 전구 : 1, 꺼진 전구 : 0 인 문자열로 입력을 줌
     • 1->0, 0->1 이런 상태변화가 없을수록 좋은 배치
     • 전구를 묶음(묶음은 순서변화 X)을 나열했을 때, 상태변화의 최소 횟수 출력하라는 문제
   • 이해
     • 전구 묶음안에서는 순서를 바꾸지 못하므로, 한 문자열(전구문자열)과 다른문자열이 이어질때 나타나는 상태변화에 주목하면 된다. 즉 문자열에서 처음과 끝만 보면 해결이 가능할것이라 생각함.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 입출력 예제를 이용해 나타내 보았고, 위 과정에서 처음과 끝만 봐도 해결이 될것이라 생각했다.
3. 문제를 어떻게 해결할 것인가

   • 

   • 1st 접근) 
     문자열의 끝과 끝을 보면 된다고 생각했으므로, 나올 수 있는 경우는 "00, 01, 10, 11"이다.
     2개씩 더한다고 생각했을때 순서상관있게 더하면 밑의 16가지 경우가 되므로 우선 다 적어보았다.
     언제 횟수가 1이 추가되는지, 두 수를 더했을 때(나열해서 붙인다는 개념) 오로지 1만 나오는지 0만 나오는지 더하기 순서를 바꾸면 0과 1 둘다 가능한지 순서가 고정인지 등을 분석하려 했다. 
     규칙이 잡히긴 했지만 이를 코드로 구현하기란 매우 난해해 보여 dp점화식을 세우지 못했고, 다른 방법을 찾아보았다. 여기서 규칙찾는다고 많은 시간을 소모했다...
   • 2st 접근)
     첫번째 접근처럼 규칙이 확실하게 보이지 않았으니, 이를 순열로 나열해서 계산하는 방법밖에 없다고 생각했다. 
     그래서 순열을 DFS로 구현하여 순열배열을 뽑아내기로 했다.
4. 위 계획을 검증
   • 두번째 접근의 경우 사실상 완전탐색이니 검증할 필요는 없다고 생각한다.
5. 계획 수행 (실제코드 작성)
   

   • import java.util.*;
     import java.io.*;
     
     public class Main{
         static int N,sum=0;
         //lights는 전구 문자열 배열, startEnd는 첫글자와 끝글자를 붙여 저장한 문자열 배열
         static String[] lights, startEnd; 
         //combList는 순열로 뽑아낸 조합들이 담겨있는 리스트
         static List<String> combList;
         //한 문자열당 얼마나 상태변화가 일어났는지에 대한 횟수가 저장된 정수형 배열
         static int[] changeLights;
         //DFS를 위한 방문여부
         static boolean[] vis;
     
         public static void main(String[] args) throws IOException {
             //System.setIn(new FileInputStream("src/input.txt"));
     
             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
             N = Integer.parseInt(br.readLine());
             lights = new String[N];
             startEnd = new String[N+1];
             combList = new ArrayList<>();
             changeLights = new int[N];
     
             startEnd[0]="";
             for (int n = 0; n < N; n++) {
                 lights[n] = br.readLine();
                 //입력과 동시에 몇번 바뀌는지 저장
                 for (int len = 0; len < lights[n].length()-1; len++) {
                     if(lights[n].charAt(len)!=lights[n].charAt(len+1)){
                         changeLights[n]+=1;
                     }
                 }
                 sum+=changeLights[n];
                 //System.out.println(changeLights[n]+" "+sum);
                 startEnd[n+1] = lights[n].charAt(0)+""+lights[n].charAt(lights[n].length()-1);
             }
     
             // startEnd의 순열조합을 리스트로 만들기
             vis = new boolean[N+1];
             DFS(0, 1,"");
             //System.out.println("combList : "+combList);
     
     		// DFS를 통해 구한 순열을 반복문을 돌리며 상태변화가 가장 최소로 일어난 값을 찾는 과정
             int res = Integer.MAX_VALUE;
             for (int combNumberOf = 0; combNumberOf < combList.size(); combNumberOf++) {
                 int localSum = 0;
                 for (int ch = 1; ch < combList.get(combNumberOf).length()-1; ch+=2) {
                     if(combList.get(combNumberOf).charAt(ch)!=combList.get(combNumberOf).charAt(ch+1)){
                         localSum+=1;
                     }
                 }
                 res = Math.min(res,localSum);
                 if(res==0){
                     break;
                 }
             }
             System.out.println(res+sum);
         }
     
         private static void DFS(int i, int depth, String comb) {
             //1.체크인
             vis[i] = true;
             comb += startEnd[i];
             //2.목적지인가
             if(depth==N+1){
                 combList.add(comb);
             }
             //3.연결되어있는가
             for (int j = 0; j < N+1; j++) {
                 //4.갈수있는가
                 if(!vis[j]){
                     //5.간다
                     DFS(j,depth+1,comb);
                 }
             }
             //6.체크아웃
             vis[i] = false;
         }
     }

<결과>

DFS를 구현하다가 vis크기와 startEnd크기를 잘못 잡아, 제대로된 순열조합이 나오지 못해 틀렸었다.