[백준 9202번] Boggle (java)

9202번: Boggle

 

DFS와 트라이 알고리즘을 통해 문제를 해결하였다.

 

게임 사전에 등재된 단어들을 트라이에 넣는다.

각 보드마다 DFS방식으로 접근하면서 여태까지 지나온 알파벳들로 이루어진 단어가 트라이에 포함되어 있는지를 확인한다.

문제에서 같은 단어를 여러 번 찾은 경우는 하나로 간주한다고 했으므로 중복을 피하기 위해 찾은 단어를 HashSet에 넣어주었다. 

 

기존의 트라이의 contains() 메서드는 true 혹은 false를 반환하였다.특정 단어에 트라이에 포함되어 있으면 true, 포함되어 있지 않으면 false 

 

아래 코드는 일반적인 트라이의 contains() 메서드이다.

		public boolean contains(String word) {

			TrieNode thisNode = rootNode;

			for (int i = 0; i < word.length(); i++) {
				char ch = word.charAt(i);

				thisNode = thisNode.getChildNodes().get(ch);

				if (thisNode == null)
					return false;

			}

			return thisNode.isLastChar();
		}

 

위 코드에서는 false를 반환하는 경우를 두 가지로 나눌 수 있다.

 

1. 찾으려는 단어에 속한 알파벳 자체가 트라이에 없는 경우 -> thisNode == null

 

   ex) 트라이에 "ABCDE" 단어가 있고, 찾으려는 단어는 "AG"인 경우

        : 아예 'G'라는 알파벳 자체가 없다.

 

2. 찾으려는 단어의 알파벳은 모두 트라이에 있으나, 마지막 알파벳이 isLastChar = false 인 경우

    -> thisNode.isLastChar() = false

 

    ex) 트라이에 "ABCDE" 단어가 있고, 찾으려는 단어가 "ABC"인 경우 : 

         "ABC"가 "ABCDE"의 일부로써 존재하나, 'C'에 해당하는 노드의 isLastChar는 false이다.

 

 

이 경우, contains() 메서드가 false를 반환하면 두 가지 중 어떤 케이스인지 알 수가 없다.

그러나 이 문제에서는 이 두가지 경우를 구분해야 한다.

 

만약 1번같은 경우라면 더 이상 DFS 탐색을 진행할 필요가 없게 된다.

"AG"가 존재하지 않는데, "AGB" 혹은 "AGED"역시 존재할 리가 없기 때문이다.

즉, 여기서 계속 탐색을 진행하면 시간만 낭비하는 꼴이 된다.

 

반면 2번같은 경우라면, 여태까지 단어로는 트라이에 존재하지 않는다고 해도, 탐색을 진행하다보면

트라이에 속할 수가 있다.

"ABC"는 트라이에 존재하지 않지만, 탐색을 계속 진행해서 "ABCDE"가 되었다면, 이 때는 트라이에 존재하기 때문이다. 즉, 좀 더 탐색을 진행할 필요가 있다.

 

따라서 나는 이 두 가지를 구분하기 위해 기존의 contains()의 반환형을 int형으로 변경하였다.

1번의 경우에는 -1을 반환하고, 2번의 경우에는 0을 반환하도록.

		public int contains(String word) {

			TrieNode thisNode = rootNode;

			for (int i = 0; i < word.length(); i++) {
				char ch = word.charAt(i);

				thisNode = thisNode.getChildNodes().get(ch);

				if (thisNode == null)
					return -1;
			}

			return thisNode.isLastChar() ? 1 : 0;
		}

 

 

그런데 정말 어이없는 부분에서 한참을 고생했다.

나는 DFS 탐색을 진행하면서 재귀함수를 호출할 때마다 새로운 탐색 위치(nr, nc)에 존재하는

알파벳(board[nr][nc])을 기존의 StirngBuilder에 추가했다.

 

그런데 몇 시간을 찬찬히 살펴보고 하나하나 뜯어보았지만, 잘못 짜여진 코드가 없음에도 불구하고 "틀렸습니다"가 나왔다.

 

그러다가 main()에서 dfs()메서드를 호출할 때,

new StringBuffer(board[r][c]) 부분을 new StringBuffer(board[r][c]+"")로 수정했더니 정답이 떴다.

StringBuffer() 생성자를 호출할 때 문자열을 인자로 넣어줘야 하는건데, char형을 넣어준 것이 문제였다.

이거 때문에 거의 몇시간을 허비했다...

 

기존 코드 : 

			for (int r = 0; r < 4; r++) {
				for (int c = 0; c < 4; c++) {
					visited[r][c] = true;
					dfs(board, r, c, new StringBuilder(board[r][c]));
					visited[r][c] = false;
				}
			}

수정 코드 : 

			for (int r = 0; r < 4; r++) {
				for (int c = 0; c < 4; c++) {
					visited[r][c] = true;
					dfs(board, r, c, new StringBuilder(board[r][c] + ""));
					visited[r][c] = false;
				}
			}

 

 

 

 

전체 코드 :