BOJ G4 9177 단어섞기 JAVA

9177번: 단어 섞기

---

문제 읽기

문제를 처음에 읽었을 때에는 모든 경우의 수를 따지는 방법을 생각했다. 단순하게 생각하면 dfs가 직관적이라 dfs를 생각했지만, 복잡도를 생각했을 때 단어의 길이가 200이기 때문에 dfs를 수행하면 지수 시간이기 때문에 불가능했다.

그래서 bfs로 접근했다.

---

문제 풀기

bfs로 풀었는데, 사실 처음에는 visited가 필요 없다고 생각했다. 처음에 다음 그림을 그렸었다.

이렇게 오른쪽, 아래쪽 두 방향으로 내려가면 경우의 수를 구했을 때 방문 처리는 안해도 되지 않을까 생각했다. 하지만 내 착각이었다. 어김없이 메모리 초과가 나왔다..!!

 

좀 찾아보고 깨달았다. 문자열이 어떻게 주어지느냐에 따라서 한 지점으로 가는 데에도 여러 개의 길이 충분히 나올 수 있고, 이 여러 개의 길을 모두 탐색하는 것은 불필요하므로, 방문 처리를 해주어야 한다는 것이다.

 

쉽게 예를 들어 다음과 같은 경우가 있을 수 있다.

따라서 visited 배열이 필요했고, 추가해주었다.

 

하지만.. 기존에 풀었던 방식은 visited가 필요 없을 것이라 생각해서 인덱스가 -1인 부분도 있었다. 기존 코드는 다음과 같았다.

    static int[] dr = {0, 1};
    static int[] dc = {1, 0};
    private static boolean bfs(String str1, String str2, String result) {
        Queue<Pos> q = new ArrayDeque<>();
        if (str1.charAt(0) == result.charAt(0))
            q.offer(new Pos(0, -1, 0));
        if (str2.charAt(0) == result.charAt(0))
            q.offer(new Pos(-1, 0, 0));

//        System.out.println(result);
        boolean canMake = false;
        while(!q.isEmpty()){
            Pos cur = q.poll();
//            System.out.println(cur.r + " " + cur.c);
//            System.out.println(cur.depth);
            if (cur.depth == result.length()){
                canMake = true;
                break;
            }

            for (int di = 0; di < 2; di++){
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < str1.length() && nr >= 0 && (str1.charAt(nr) == result.charAt(cur.depth))){
                    q.offer(new Pos(nr, nc, cur.depth+1));
                }
                if (nc < str2.length() && nc >= 0 && (str2.charAt(nc) == result.charAt(cur.depth))){
                    q.offer(new Pos(nr, nc, cur.depth+1));
                }
            }
        }

        return canMake;
    }

 

그래서 여기에 visited를 추가하려니 너무 머리가 아팠다..!!!

 

안에 추가하자니 인덱스가 -1인 부분이 있어서 에러가 떴고, 처리해주자니 조건식이 너무 복잡해져서 이게 맞나 싶었다.

 

첫 번째 원소부터 검사하면서, visited를 추가하기 위해서는 다음과 같이 v큐에서 꺼낼 때 visited를 검사하는 방법을 선택하였다.

그래서 다음과 같이 bfs 코드를 변경했다.

            Queue<Pos> q = new ArrayDeque<>();
            boolean[][] visited = new boolean[str1.length()+1][str2.length()+1];
            q.offer(new Pos(0, 0, 0));

            boolean canMake = false;
            while(!q.isEmpty()){
                Pos cur = q.poll();

                if (visited[cur.idx1][cur.idx2]) continue;
                visited[cur.idx1][cur.idx2] = true;

                if (cur.depth == result.length()){
                    canMake = true;
                    break;
                }

                //idx1이 1 증가된 경우
                if (cur.idx1 < str1.length() && (str1.charAt(cur.idx1) == result.charAt(cur.depth))){
                    q.offer(new Pos(cur.idx1+1, cur.idx2, cur.depth+1));
                }
                //idx2가 1 증가된 경우
                if (cur.idx2 < str2.length() && (str2.charAt(cur.idx2) == result.charAt(cur.depth))){
                    q.offer(new Pos(cur.idx1, cur.idx2+1, cur.depth+1));
                }
            }

 

이렇게 하니 해결되었다!

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_G4_9177_단어섞기 {
    static class Pos{
        int idx1, idx2;
        int depth;
        public Pos(int idx1, int idx2, int depth){
            this.idx1 = idx1;
            this.idx2 = idx2;
            this.depth = depth;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= T; i++){
            StringTokenizer st = new StringTokenizer(in.readLine());
            String str1 = st.nextToken();
            String str2 = st.nextToken();
            String result = st.nextToken();

//            boolean canMake = bfs(str1, str2, result);

            Queue<Pos> q = new ArrayDeque<>();
            boolean[][] visited = new boolean[str1.length()+1][str2.length()+1];
            q.offer(new Pos(0, 0, 0));

            boolean canMake = false;
            while(!q.isEmpty()){
                Pos cur = q.poll();

                if (visited[cur.idx1][cur.idx2]) continue;
                visited[cur.idx1][cur.idx2] = true;

                if (cur.depth == result.length()){
                    canMake = true;
                    break;
                }

                //idx1이 1 증가된 경우
                if (cur.idx1 < str1.length() && (str1.charAt(cur.idx1) == result.charAt(cur.depth))){
                    q.offer(new Pos(cur.idx1+1, cur.idx2, cur.depth+1));
                }
                //idx2가 1 증가된 경우
                if (cur.idx2 < str2.length() && (str2.charAt(cur.idx2) == result.charAt(cur.depth))){
                    q.offer(new Pos(cur.idx1, cur.idx2+1, cur.depth+1));
                }
            }

            sb.append("Data set ").append(i).append(": ").append((canMake)? "yes" : "no").append("\\n");
        }
        System.out.println(sb);
    }

}