📃프로그래머스 - 아이템 줍기

DFS/BFS , LEVEL3

코드

    int sx, sy, ex, ey;
    int[][] map = new int[102][102];
    boolean[][] chkMap = new boolean[102][102];
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        sx = characterX * 2;
        sy = characterY * 2;
        ex = itemX * 2;
        ey = itemY * 2;


        /* 1. map에 주어진 사각형 영역을 -1 로 채운다. */
        for(int[] r : rectangle){
            for(int x=r[0]*2; x<=r[2]*2; x++){
                for(int y=r[1]*2; y<= r[3]*2; y++){
                    map[x][y] = -1;
                }
            }
        }

        /* 2. 지뢰찾기 하듯이.. chkMap 에 테두리만 부분만 true 로 남긴다. */
        for(int i=1 ; i< 101 ; i++){
            for(int j=1; j < 101 ; j++){
                if(map[i][j] != -1)continue;
                if(map[i-1][j-1] + map[i-1][j] + map[i-1][j+1] + map[i][j-1] + map[i][j+1] + map[i+1][j-1] + map[i+1][j] + map[i+1][j+1] > -8){
                    chkMap[i][j] = true;
                }
            }
        }

        bfs(sx, sy, 0);

        return map[ex][ey] / 2;
    }


    public void bfs(int x, int y, int cnt){

        if(map[x][y] == -1){
            // map 에 현재 카운트수 기록
            map[x][y] = cnt;

        } else{
            // 이미 방문한 적이 있는 경우(목적지) 더 적은 cnt 채택
            map[x][y] = Math.min(map[x][y], cnt);
        }
        if(x==ex && y==ey ) {
            // 탈출 조건
            return;
        }

        /* 3. 테두리를 따라 갈 수 있는 방향으로 계속 간다. */
        // 목적지를 제외하고 한번 간 곳은 가지 않는다.
        if((x-1 == ex && y == ey) || (chkMap[x-1][y] && map[x-1][y] == -1)) bfs(x-1, y, cnt + 1);
        if((x+1 == ex && y == ey) || (chkMap[x+1][y] && map[x+1][y] == -1)) bfs(x+1, y, cnt + 1);
        if((x == ex && y-1 == ey) || (chkMap[x][y-1] && map[x][y-1] == -1)) bfs(x, y-1, cnt + 1);
        if((x == ex && y+1 == ey) || (chkMap[x][y+1] && map[x][y+1] == -1)) bfs(x, y+1, cnt + 1);

    }

풀이

1. map에 주어진 사각형 영역을 -1 로 채운다.

2. 지뢰찾기 하듯이.. chkMap 에 테두리만 부분만 true 로 남긴다.

3. 테두리를 따라 갈 수 있는 방향으로 간다.

x, y 현재 위치 기준으로 T 인곳으로 가면서 cnt를 map 에 기록한다.

4. 목적지에 있는 cnt 수를 가져온다.

2를 곱하여 계산했으므로 나누기 2 하면 답!

프로그래머스 - 과제 진행하기

📓풀이

과제가 끝날 시간과 다음과제가 시작될 시간의 차인 remainTime 이 핵심값

remainTime == 0 과제가 끝남과 동시에 다음 과제 시작

remainTime < 0 과제를 다 못했는데 다음 과제가 시작됨 과제를 미뤄야함

remainTime > 0 과제를 다 했는데 다음 과제까지 시간이 남음 미뤄둔 과제가 있다면 할 수 있음

• 과제를 둘로 나누어 생각한다. 계획된 과제와 미뤄둔 과제

• 계획된 시간에 맞춰 과제를 진행한다. 위 처럼 remainTime을 계산하여 시간이 맞지 않으면 과제를 미루거나 밀린 과제를 한다.

• 마지막 시간에 시작하는 과제는 중간에 그만둬야하는 경우가 없다. → 다음 과제 시작시간을 예상종료시간(start + play)과 똑같이 정하면 된다.

• 마지막 과제가 끝나면 미뤄둔 과제들은 play 시간과 상관 없이 차례로 끝내면된다.

📓코드

 public List<String> solution(String[][] plans) {
    List<String> answer = new ArrayList<>();

    PriorityQueue<Integer> startQ = new PriorityQueue<>();
    Map<Integer, String> startNameMap = new HashMap<>();
    Map<String, Integer> namePlayMap = new HashMap<>();

    for(String[] plan : plans){
        String name = plan[0];
        int start = Integer.parseInt(plan[1].substring(3,5)) + (Integer.parseInt(plan[1].substring(0,2)) * 60);
        int playTime = Integer.parseInt(plan[2]);
        startQ.add(start);
        startNameMap.put(start, name);
        namePlayMap.put(name, playTime);
    }        

    Stack<String> postponedTask = new Stack<>();
    //1. 주어진 시간대로 과제하기
    while(!startQ.isEmpty()){
        int now = startQ.poll();
        String name = startNameMap.get(now);        //해야할 과제명
        int endTime = now + namePlayMap.get(name);  //예상 종료시간
        int nextStartTime = (!startQ.isEmpty()) ? startQ.peek() : endTime;// 다음 과제 시작 시간
        //1-1. 시간 계산
        int remainTime = nextStartTime - endTime;

        //1-2. A. 과제를 다했다
        if(remainTime >= 0){
            answer.add(name);//A-1. 완료처리
            while (remainTime > 0){//A-2. 남은 시간 활용하기
                if(!postponedTask.isEmpty()){//A-3. 미뤄둔 과제가 있다.
                    String postponed = postponedTask.peek();
                    int postponedTime = namePlayMap.get(postponed);
                    if (postponedTime <= remainTime){//A-3. 남은 시간동안 완료함(완료처리)
                        answer.add(postponedTask.pop());
                    }else{//A-3. 남은 시간동안 다 못함
                        namePlayMap.put(postponed, postponedTime - remainTime);
                    }
                    remainTime -= postponedTime;
                }else break;
            }
        }
        //1-2. B. 과제를 다 못함..
        else{
            namePlayMap.put(name, Math.abs(remainTime));
            postponedTask.push(name);//B-1. 과제 미루기
        }
    }
    //2. 미뤄둔 과제 차례로 완료하기
    while(!postponedTask.isEmpty()){
        answer.add(postponedTask.pop());
    }
    return answer;
}

📃프로그래머스 - 가장 먼 노드

그래프 카테고리의 level3문제다.

처음 풀어보는 그래프 문제라 처음에 헤맸다. 그래도 이 문제를 풀면서 언제 bfs를 써야하는지 감이 좀 잡혔다.

bfs를 공부할겸 인접리스트로 푸는 방법, 인접행렬로 푸는 방법 두 가지로 풀어봤다.

🐴 bfs

bfs 문제를 푸는 방법은 인접리스트를 이용하는 방법, 인접행렬을 이용하는 방법 두가지가 있다.

푸는 방법은

• 인접리스트 : 존재하는 간선에 대해서만 탐색을 한다.
• 인접행렬 : 모든 정점에 대해 탐색

시간복잡도로 보면
G: 그래프, V: 정점, E: 간선

• 인접리스트 : O(V+E)
• 인접행렬 : O(V^2)

🐴 로직 - 인접리스트

** 테스트케이스 *

기본 테스트케이스를 조금 변형한 아래의 테스트케이스로 로직을 설명한다.
6, [[3, 6], [1, 3], [1, 2], [2, 4], [5, 2]]

1. 인접 리스트 만들기

간선의 방향이 양방향 이므로 인접 리스트 양쪽 노드에 모두 추가

2. bfs로 탐색

시작 노드가 1(0)로 정해져있다. bfs메서드에 탐색해야할 노드를 큐로 넘겨준다.

🐴 코드 - 인접리스트

public int solution(int n, int[][] edge) {
    /* 인접 리스트에 데이터 추가*/
    //인접리스트 생성
    List<List<Integer>> adList = new ArrayList<>();
    //노드수만큼 초기화
    for (int i = 0; i < n; i++) {
        adList.add(new ArrayList<Integer>());
    }
    //데이터 추가
    for (int[] e : edge) {
        adList.get(e[0] - 1).add(e[1] - 1);
        adList.get(e[1] - 1).add(e[0] - 1);
    }

    Queue<Integer> q = new LinkedList<>();
    q.offer(0);

    boolean[] check = new boolean[n];
    check[0] = true;

    return bfs(adList, q, check);
}


public int bfs(List<List<Integer>> adList, Queue<Integer> q, boolean[] check) {
    int answer = q.size();        
    Queue<Integer> q2 = new LinkedList<>();

    /* 1. 다음 depth에 해당하는 노드를 확인하고 큐에 담는다.*/
    while(!q.isEmpty()) {
        for (int i : adList.get(q.poll())) {
            if (!check[i]) {
                check[i] = true;
                q2.offer(i);
            }
        }
    }
    /* 2. 다음 depth가 없다면 return */
    if(q2.size()==0) return answer;
    /* 2. 있다면 bfs */
    answer = bfs(adList, q2, check);

    return answer;
}

🐴 로직 - 인접행렬

1. 인접행렬 만들기

boolean타입의 2차원 배열로 행렬을 사용했다.

🐴 코드 - 인접행렬

public int solution(int n, int[][] edge) {
    /*1. 인접행렬에 담기  */
    boolean[][] arr = new boolean[n+1][n+1];

    for(int[] e : edge) {
        arr[e[0]][e[1]] = true;
        arr[e[1]][e[0]] = true;
    }

    Queue<Integer> q = new LinkedList<Integer>();
    q.offer(1);
    boolean[] check = new boolean[n+1];
    check[1] = true;
    /* 2. bfs*/
    return bfs(arr, q, check);
}


public int bfs(boolean[][] arr, Queue<Integer> q, boolean[] check) {
    int size = q.size();    //현제 Depth의 노드 수 

    /* 다음 탐색해야할 노드들 큐에 담기  */
    Queue<Integer> q2 = new LinkedList<Integer>();
    while(!q.isEmpty()) {
        for(int i = 1; i < check.length ; i++) {
            if(arr[q.peek()][i] && !check[i]) {
                check[i] = true;
                q2.offer(i);
            }
        }
        q.poll();
    }
    /* 다음 탐색해야할 노드가 없다면(지금이 마지막 depth라면) size 리턴*/
    if(q2.isEmpty()) {
        return size;
    }

    return bfs(arr, q2, check);
}

프로젝트를 빌드하고 라이브러리를 관리해주는 도구

프로젝트를 진행하게 되면 단순히 자신이 작성한 코드만으로 개발하는 것이 아니라 많은 라이브러리들을 활용해서 개발을 하게 된다. Maven은 내가 사용할 라이브러리 뿐만 아니라 해당 라이브러리가 작동하는데 필요한 다른 라이브러리들까지 관리하여 네트워크를 통해 자동으로 다운 받아준다.

Maven은 프로젝트의 전체적인 라이프사이클을 관리하는 도구이며, 많은 편리함과 이점이 있어 널리 사용되고 있다. 기존에는 Ant가 많이 사용되었지만 Maven이 Ant를 넘어서 더 많은 개발자들이 사용하게 되었고 비교적 최근에는 Gradle이 새롭게 나와 사용되고 있다.

maven의 LifeCycle

https://myjamong.tistory.com/153

maven 에서는 미리 정의하고 있는 빌드 순서가 있으며 이 순서를 라이프사이클이라고 한다. 라이프 사이클의 가 빌드 단계를 Phase라고 하는데 이런 Phase들은 의존관계를 가지고 있다.

각 phase에는 plugin이 존재하고 해당 plugin에서 수행 가능한 명령을 goal 이라고 합니다.

Goals의 ":" 기준으로 앞은 plugin을 의미하고 뒷 부분은 해당 plugin의 goal을 뜻합니다.

< 기본(Default) 라이프사이클>

• Validate : 프로젝트가 올바른지 확인학고 필요한 모든 정보를 사용할 수 있는 지 확인하는 단계
• Compile : 프로젝트의 소스코드를 컴파일하는 단계

     성공적으로 컴파일되면 target/classes 폴더가 만들어지고 컴파일된 class파일이 생성된다.

• Test : 유닛(단위) 테스트를 수행하는 단계(테스트 실패시 빌드 실패로 처리, 스킵 가능)
• Package : 실제 컴파일된 소스 코드와 리소스들을 jar등의 배포를 위한 패키지로 만드는 단계
• Verify : 통합테스트 결과에 대한 검사를 실행하여 품질 기준을 충족하는지 확인하는 단계
• Install : 패키지를 로컬 저장소에 설치하는 단계 (local repository 즉, maven이 설치되어 있는 PC에 배포)
• Deploy : 만들어진 Package를 원격 저장소에 release하는 단계

< clean 라이프사이클>

• Clean : 이전 빌드에서 생성된 파일들을 삭제하는 단계

< site 라이프사이클>

• Site : 프로젝트 문서를 생성하는 단계

POM - Project Object Model

pom은 Project Object Model 의 약자로 이름 그대로 Project Object Model의 정보를 담고있는 파일이다. 이 파일에서 주요하게 다루는 기능들은 다음과 같다.

• 프로젝트 정보 : 프로젝트의 이름, 개발자 목록, 라이센스 등
• 빌드 설정 : 소스, 리소스, 라이프 사이클별 실행한 플러그인(goal)등 빌드와 관련된 설정
• 빌드 환경 : 사용자 환경 별로 달라질 수 있는 프로파일 정보
• POM연관 정보 : 의존 프로젝트(모듈), 상위 프로젝트, 포함하고 있는 하위 모듈 등

POM은 pom.xml파일을 말하며 Maven의 기능을 이용하기 위해 POM이 사용된다.

프로그래머스-등굣길

** 다이나믹 프로그래밍이란? ** 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

최단경로 문제도 기존 경로 값을 이용하여 쉽게 구할 수 있다.

🏫풀이

예제의 기본 테스트케이스를 준비했다. 아래의 지도에 경로의 수를 기록하면 된다.

1. 초기화

• 시작점은 (1,1)로 정해져 있으므로 첫칸(1,1)은 "1"로 설정한다.
• 웅덩이를 식별하기 위해 음수 "-1" 로 설정한다.
• 편의를 위해 0번째 행과 열은 비워둔다. (깍두기)

** 2. 경로 계산 **

• 등굣길은 오른쪽과 아래 방향으로만 갈 수 있으므로

• ** 이 길을 지나갈 수 있는 경우의 수 = 위쪽 길의 경우의 수 + 왼쪽 길의 경우의 수 **

• 첫칸(1,1)은 생략하고 왼쪽부터 아래로 차례대로 왼쪽과 위쪽의 값을 더해준다.

• 웅덩이가 나오면 0으로 설정해주고 더한다. _ 첫번째 열과 첫번재 행의 계산을 편하게 하기 위해 '2.초기화' 과정에서 깍두기 줄을 추가 해줬다. _

** 3. 정답은 4!! **

코드

public int solution(int m, int n, int[][] puddles) {
    //배열 생성 및 초기화
    int[][] route = new int[m+1][n+1];

    route[1][1] = 1;

    /* 2. 웅덩이 -1 으로 표시 */
    for(int[] p : puddles) {
        int i = p[0];
        int j = p[1];
        route[i][j] = -1;
    }

    /* 3. 경우의 수 계산 */
    for(int i=1 ; i <= m ; i++) {
        for(int j=1 ; j <= n ; j++) {
            if(i == 1 && j == 1) continue; //첫칸은 생략
            if(route[i][j] < 0) {//웅덩이
                route[i][j] = 0;
                continue; 
            }
            route[i][j] = (route[i][j-1]  % 1000000007) + (route[i-1][j] % 1000000007);
        }
    }

    return route[m][n] % 1000000007;
}

코딩테스트 연습 - 주차 요금 계산

🚗풀이

1. 시간 기록하기

   • Map<차량번호, 주차시간> 을 사용하여 In 일때는 "- 시간", out 일때는 "+ 시간" 을 한다.

2. 정산하기

   • map을 돌며 주차요금을 계산한다.

     2-1. 미출차 차량 시간 계산

   • 미출차 차량(시간이 0 or 음수인 차량)인 경우 12:59 기준으로 시간 계산

     2-2. 정산하기

   • 주어진 요금표 정보로 계산

🚗코드

import java.util.*;
class Solution {
    public List<Integer> solution(int[] fees, String[] records) {

        Comparator<String> comparator = (s1, s2)->s1.compareTo(s2);        
        Map<String, Integer> timeMap = new TreeMap<>(comparator);

        final int basetime  = fees[0]; //기본 시간
        final int baseFee   = fees[1]; //기본 요금
        final int plustime  = fees[2]; //추가 시간
        final int plusFee   = fees[3]; //추가 요금

        /* 기록하기
         * Map<차번호, 시간>*/
        for(String record : records) {
            String[] r = record.split(" ");
            int time = Integer.parseInt(r[0].split(":")[0]) * 60 + Integer.parseInt(r[0].split(":")[1]);
            String carNum = r[1];
            //IN 이면 "-시간" OUT이면 "시간"
            time = (r[2].equals("IN")) ? time*-1 : time;
            timeMap.put(carNum, timeMap.getOrDefault(carNum, 0) + time);

        }

        /* 정산하기 */
        timeMap.forEach((key, value) -> {
            //1. 출차 내역 없는 차량(시간이 음수값 or 0 인 차량) 시간 계산
            int howlong = (value <= 0) ? value + 1439 : value;
            //2. 정산
            int howmuch = (howlong < basetime) ? baseFee : baseFee + (int) Math.ceil(((float)(howlong - basetime) / plustime)) * plusFee; 
            timeMap.put(key, howmuch);
        });

        return new ArrayList<>(timeMap.values());
    }
}

📃프로그래머스 - 정수 삼각형

동적계획법(Dynamic Programming) 카테고리의 level3 문제다.

🔺동적프로그래밍

처음엔 동적프로그래밍이 뭔지 공부도 안하고 모든 경우의 수를 재귀로 풀려고 했다. 역시나 효율성 제로ㅎ

동적프로그래밍이 무엇인지 찾아보니..

< 동적프로그래밍 >

• 큰 문제를 작은 문제로 분할하여 해결하는 알고리즘이다.
• 작은 문제는 반복되지 않고 풀때마다 항상 값이 같다.
• 작은 문제의 답을 어딘가에 메모 해놓는다. → Memoization

설명만 읽고는 잘 와닿지 않았다. 문제를 풀며 조금씩 감이 잡혔다.

이 문제는 위에서 아래로 대각선 방향으로 내려오며 더했을 때 가장 큰 경우를 찾는 문제이다.

🔺로직

이 문제의 로직은 간단하다. 대각선 방향으로 한줄씩 내려오며 숫자를 더하는걸 작은 문제로 나눠서 풀면 된다. 작은 문제의 답은 풀때마다 항상 같다.

아래가 이 문제의 작은문제다. 노랑(자신 + 왼쪽 대각선) vs 초록(자신 + 오른쪽 대각선) 이 두개를 비교하여 더 큰수가 해당 자리의 답이 된다.

두번째 줄 부터

1. 줄의 왼쪽 끝 숫자는 자신과 윗줄의 왼쪽 숫자와 더한다.

2. 왼쪽과 더한 수 , 오른쪽과 더한 수 두 개를 비교하여 더 큰수가 해당 자리의 답이 된다.

3. 오른쪽 끝 숫자는 자신과 윗줄의 오른쪽 숫자와 더한다.

위 과정을 반복하여 memoization을 거치면 오른쪽과 같이 된다. 이 중 가장 큰 수 가 문제의 답이된다.

🔺코드

for(int i = 1; i < n ; i++) {
    for(int j = 0; j < triangle[i].length ; j++) {

        if(j == 0) {//왼쪽 끝
            triangle[i][j] += triangle[i-1][j];
        }
        else if(j == i) {//오른쪽 끝
            triangle[i][j] += triangle[i-1][j-1];
        }
        else {
            triangle[i][j] += Math.max(triangle[i-1][j], triangle[i-1][j-1]);
        }

        answer = Math.max(answer, triangle[i][j]);
    }
}
return answer;

[📃프로그래머스 - 베스트앨범] (https://programmers.co.kr/learn/courses/30/lessons/42579)

💿📀 풀이

문제의 조건에 따라 고려 대상의 우선순위는 아래와 같다.

** 장르별 총 재생수 → 앨범별 재생 수 → 앨범의 고유번호 **

장르별 정렬이 우선이기 때문에 장르명이 Key값인 Map을 이용해 풀어야 할 것 같은데 value를 어떻게 잡을지 고민이 됐다.

장르명에 따라 총 재생수와 앨범의 정보(재생수 와 고유번호)가 필요했다. 앨범의 고유번호는 plays 배열의 인덱스다. 고유번호만 있으면 앨범의 재생수는 plays[고유번호]로 알 수 있다.

따라서, value로 필요한 정보를 총재생수와 고유번호 리스트로 정했다. 둘의 타입이 달라 Genre라는 클래스를만들었다.

Genre클래스는 장르별 총재생수를 누적할 수 있는 total 변수와 앨범의 고유번호를 담는 albumList 리스트로 구성했다.

아래와 같은 Map 구조로 문제를 풀었다.

💿📀 로직

입력데이터

문제에 나와있는 기본 테스트케이스이다.

genres : ["classic", "pop", "classic", "classic", "pop"]
plays  : [500, 600, 150, 800, 2500]

1. 입력 데이터를 Map에 넣는다.

→ 데이터가 장르별로 구분된다.

2. 총재생수로 정렬

이제 장르명은 필요없다! Map의 value값을 List로 변환 후 장르별 총재생수로 List를 정렬한다. 사실 List로 변환하지 않고 Map 그대로 정렬하려고 했는데, Map 정렬하는 코드가 좀 더러워서 간단하게 List로 변환하여 정렬하였다.

3. 마지막, 장르별로 베스트 앨범 두개를 선정

앨범별 재생수를 비교하기 위해 우선순위큐(PriorityQueue)에 고유번호와 재생수를 put해준 후 베스트앨범 두개or한개를 poll해주면 답이 나온다. 답!!

💿📀 코드

public List<Integer> solution(String[] genres, int[] plays) {
    List<Integer> answer = new ArrayList<Integer>();

    Map<String, Genre> gMap = new HashMap<>();

    /* 1. map에 장르별로 데이터 추가 */
    for(int i=0; i< genres.length ; i++) {        
        if(gMap.containsKey(genres[i])) {                
            Genre oriGen = gMap.get(genres[i]);
            oriGen.addGenre(plays[i], i);
            gMap.put(genres[i], oriGen);
        }
        else {
            gMap.put(genres[i], new Genre(plays[i], i));
        }
    }

    /* 2. 장르별 정렬 */
    List<Genre> gList = new ArrayList<>(gMap.values());
    //총재생수를 이용하여 비교
    gList.sort((o1, o2)-> o2.getTotal() - o1.getTotal());

    /* 3. 장르별 베스트앨범 2개 선정 */
    for (Genre list : gList) {
        /* PriorityQueue 
         * 재생수 큰 순서대로 정렬 
         * 같을 경우 앨범고유번호 순으로  */
        PriorityQueue<int[]> q = new PriorityQueue<>((o1,o2) -> {
            if(o2[1] - o1[1] == 0)
                return o1[0] - o2[0];
            else
                return o2[1] - o1[1];
        });
        // 큐에 모든 앨범 추가
        for(int i : list.getAlbumList()) {    
            int[] play = {i,plays[i]};
            q.offer(play);
        }

        // 상위 두개만 꺼낸다.
        answer.add(q.poll()[0]);
        if(!q.isEmpty())
            answer.add(q.poll()[0]);
    }

    return answer;
}

class Genre{
    int total = 0;    //총 재생 수
    List<Integer> albumList = new ArrayList<>();    //앨범 고유번호 리스트

    /**
     * 앨범 추가
     * - 재생수 누적, 앨범리스트 추가
     */
    public void addGenre(int total, int album) {
        this.total += total;
        this.albumList.add(album);
    }

    public Genre(int total, int album) {
        this.total += total;
        this.albumList.add(album);
    }

    // Getter, Setter 생략 //
}

💿📀 마무리

처음에 Map으로 풀어야되는건 알겠는데 구조 잡는데 헤맸다.

Map도 쓰고 List도 쓰고 Queue도 쓰고 너무 많이 쓴건가 싶기도하다.

더 간단하게 만들 수 있을것 같기도 하다. 담에 다시 풀어봐야지~

📄 프로그래머스 - 단어변환문제

프로그래머스 DFS/BFS 카테고리에 있는 "단어변환"문제다. DFS를 이용하여 풀었다.

📌로직

문제에 있는 테스트케이스로 그림을 한번 그려봤다.

주어진 words 리스트에 target문자열이 있는지 먼저 체크 한 후 target문자열이 있다면 아래 그림처럼 모든 경우의 수를 탐색한다.

begin 부터 시작해 변환 가능한 단어로 가지치기 하듯이 모든 경우를 모두 찾아 카운트를 한다. 가지치기(?) 한곳에서 카운트가 작은 쪽이 리턴된다. 이 과정을 반복하여 최종적으로 모든 경우의 수 중 가장 작은 값이 리턴된다.

정리하면

1. words 에 target 있는지 확인
2. 단어변환 경로 탐색
2-1. target이 되었을때 RETURN (탈출조건)
2-2. 가능한 단어 체크 후 재귀(2번으로)

📌테스트케이스

- "begin", "target", words //결과

- "hit", "cog", {"hot", "dot", "dog", "lot", "log", "cog"}    //4
- "hit", "log", {"hot", "dot", "dog", "lot", "log", "cog"}    //3
- "hit", "cog", {"cog", "log", "lot", "dog", "dot", "hot"}    //4
- "hit", "cog", {"hot", "dot", "dog", "lot", "log"}        //0
- "1234567000", "1234567899", {"1234567800", "1234567890", "1234567899"}//3

📌코드

public int solution(String begin, String target, String[] words) {
    int n = words.length;

    /* 1. words 에 target 있는지 확인*/
    int index = -1;
    for(int i = 0 ; i < n ; i++) {
        if(words[i].equals(target)) index = i;
    }
    if(index< 0) {
        return 0;
    }
    /* 2. 단어변환 경로 탐색 */
    boolean[] chk = new boolean[n];
    return dfs(begin, target, -1, words, chk, 0);
}

/**
 * 단어변환의 모든 경로 탐색 최저 카운트 수 반환
 */
public int dfs(String begin, String target, int idx, String[] words, boolean[] chk , int cnt) {        
    /* target이 되었을때 RETURN (탈출조건) */
    if(target.equals(begin)) {
        return cnt;
    }

    /* 방문체크, 카운트 */
    if(idx >= 0) chk[idx] = true;
    cnt++;

    /* 가능한 단어 체크 후 재귀 */
    int answer = chk.length;
    for(int i=0 ; i<chk.length ; i++) {            
        if(!chk[i]) {
            if(wordCheck(begin.toCharArray(), words[i].toCharArray())) {
                answer = Math.min(answer, dfs(words[i], target, i, words, chk, cnt));
                chk[i] = false;
            }
        }
    }
    return answer;
}

/**
 * 가능한 단어인지 체크 
 */
public boolean wordCheck(char[] begin, char[] target) {
    /* 한글자만 다른지 체크 */
    int cnt = 0;
    for(int j=0 ; j<begin.length ; j++) {
        if(begin[j] != target[j])
            cnt ++;
    }
    return (cnt ==1) ? true : false;
}

📌마무리

재귀 로직을 생각하느라 좀 헤맸다. 아직 재귀 문제를 풀면 뫼비우스 띠에 빠지는 느낌이다..

dfs 메서드에 파라미터가 너무 주렁주렁 달려있어서 줄이고 싶은데 일단 저게 최선이다😥

아직 BFS 알고리즘은 뭔지, DFS/BFS 중 뭘 이용해야 효율적인지 모르겠다. 다음엔 BFS 공부해서 DFS/BFS 알고리즘을 한번 정리 해봐야겠다!