프로그래머스 (Level 3) - 단어 변환

문제 설명

코딩테스트 연습 - 단어 변환

 

풀이

주어진 단어 정보를 이용해서 그래프를 생성한다. 한 문자만 빼고 나머지 문자가 같은 단어끼리 간선을 추가한다. 그래프가 완성되면 begin 단어에서 target 단어까지 경로의 길이를 반환하는 방법으로 문제를 해결하였다.

 

/** 그래프를 구성하는 각 노드의 정보를 정의한 클래스 */
static class Node {
    String word;   // 단어
    List<Node> adjacents;    // 인접한 단어들(한 문자만 차이나는 단어들)
    boolean visited;   // 방문 여부를 확인하기 위한 변수
    int depth;   // 깊이(경로의 길이를 탐색하기 위한 변수)

    Node(String word) {
        this.word = word;
        this.adjacents = new ArrayList<Node>();
        this.visited = false;
        this.depth = 0;
    }
}

그래프를 구성하는 각 노드의 정보를 클래스로써 정의한다. 각 노드는 "단어", "인접한 단어들", "방문 여부를 확인하기 위한 변수", "깊이"에 대한 정보를 가진다.

 

/** 두 개의 단어를 비교하는 메서드 */
static boolean compare(String current, String word) {
        int count = 0;

        for (int i = 0; i < current.length(); i++) {
            if (current.charAt(i) != word.charAt(i))
                count++;
        }

        if (count == 1)
            return true;
        else
            return false;
}

두 단어를 비교하는 메서드이다. 두 단어끼리 한 문자만 다른 경우에 "true"를 반환하고, 그렇지 않을 경우엔 "false"를 반환한다.

 

/** 간선 연결 */
for (int i = 0; i < nodes.length; i++) {
    for (int j = 0; j < nodes.length; j++) {
        if (compare(nodes[i].word, nodes[j].word) && !nodes[i].word.equals(nodes[j].word)) {
            nodes[i].adjacents.add(nodes[j]);
            nodes[j].adjacents.add(nodes[i]);
        }
    }
}

그래프의 간선을 추가하는 메서드이다. 두 단어를 비교해 한 문자만 다른 경우에 간선을 추가하여 그래프를 구성한다.

 

/** bfs 알고리즘을 이용해서 target 단어를 탐색하는 메서드 */
static int bfs(int start, String target) {
    int count = 0;

    Queue<Node> queue = new LinkedList<>();

    nodes[start].visited = true;

    queue.add(nodes[start]);

    while (!queue.isEmpty()) {

        Node node = queue.poll();

        if (node.word.equals(target))
            return node.depth;

        for (Node next : node.adjacents) {
            if (next.visited == false) {
                next.visited = true;
                next.depth = node.depth + 1;

                queue.add(next);
            }
        }
    }

    return 0;
}

BFS 알고리즘을 이용해서 begin 단어에서 target 단어까지 탐색 경로의 길이를 반환하는 메서드이다. 현재 탐색 노드에서부터 인접한 노드를 탐색할 때마다 "depth" 변수를 1씩 증가시킴으로써 탐색 경로를 갱신에 준다.

 

전체 소스코드

import java.io.*;
import java.util.*;

public class Solution02 {

	static Node[] nodes;

	public int solution(String begin, String target, String[] words) {
		/** 그래프 생성 */
		nodes = new Node[words.length + 1];

		nodes[0] = new Node(begin);

		for (int i = 1; i < nodes.length; i++) {
			nodes[i] = new Node(words[i - 1]);
		}

		/** 간선 연결 */
		for (int i = 0; i < nodes.length; i++) {
			for (int j = 0; j < nodes.length; j++) {
				if (compare(nodes[i].word, nodes[j].word) && !nodes[i].word.equals(nodes[j].word)) {
					nodes[i].adjacents.add(nodes[j]);
					nodes[j].adjacents.add(nodes[i]);
				}
			}
		}

		return bfs(0, target);
	}

	/** 두 개의 단어를 비교하는 메서드 */
	static boolean compare(String current, String word) {
		int count = 0;

		for (int i = 0; i < current.length(); i++) {
			if (current.charAt(i) != word.charAt(i))
				count++;
		}

		if (count == 1)
			return true;
		else
			return false;
	}

	/** bfs 알고리즘을 이용해서 target 단어를 탐색하는 메서드 */
	static int bfs(int start, String target) {
		int count = 0;

		Queue<Node> queue = new LinkedList<>();

		nodes[start].visited = true;

		queue.add(nodes[start]);

		while (!queue.isEmpty()) {

			Node node = queue.poll();

			if (node.word.equals(target))
				return node.depth;

			for (Node next : node.adjacents) {
				if (next.visited == false) {
					next.visited = true;
					next.depth = node.depth + 1;

					queue.add(next);
				}
			}
		}

		return 0;
	}

	/** 그래프를 구성하는 각 노드의 정보를 정의한 클래스 */
	static class Node {
		String word;
		List<Node> adjacents;
		boolean visited;
		int depth;

		Node(String word) {
			this.word = word;
			this.adjacents = new ArrayList<Node>();
			this.visited = false;
			this.depth = 0;
		}
	}

}

 

DFS를 이용한 풀이

import java.io.*;
import java.util.*;

public class Solution02 {
	static int answer = 0;

	static boolean[] visited;

	public int solution(String begin, String target, String[] words) {

		visited = new boolean[words.length];

		dfs(begin, target, words, 0);

		return answer;
	}

	/** dfs 알고리즘을 이용하여 target 단어 탐색 */
	static void dfs(String begin, String target, String[] words, int count) {
		if (begin.equals(target)) {
			answer = count;

			return;
		}

		for (int i = 0; i < words.length; i++) {
			if (compare(begin, words[i]) && visited[i] == false) {
				visited[i] = true;
				dfs(words[i], target, words, count + 1);
				visited[i] = false;
			}
		}
	}

	/** 두 개의 단어를 비교하는 메서드 */
	static boolean compare(String current, String word) {
		int count = 0;

		for (int i = 0; i < current.length(); i++) {
			if (current.charAt(i) != word.charAt(i))
				count++;
		}

		if (count == 1)
			return true;
		else
			return false;
	}
}

기존의 풀이 방식은 각 단어의 정보를 이용해 그래프를 구성하고, 구성된 그래프를 통해 begin 단어와 target 단어 사이의 경로의 길이를 구하는 방식이었다.

하지만, 각 단어의 방문 여부를 확인하는 배열을 선언한 후, 재귀적으로 dfs 메서드를 호출시켜 target 단어를 찾을 때까지 count 변수를 갱신시켜줌으로써 더욱 쉽게 문제를 해결할 수 있었다.