백준 12904번 A와 B (Java)

문제

---

해결 과정

---

1. BFS와 메모리 초과

---

문자열 S에서 T로 갈 수 있는 경우의 수를 그려보고, BFS를 사용하는 간단한 문제라고 생각했지만, 메모리 초과가 발생하였다.

해당 문제에서는 2ⁿ 크기로 Queue에 노드가 쌓이기 때문에 스택 오버 플로우가 발생한 것이었다.

BFS 알고리즘을 사용할 경우, 조건에 해당하는 노드만 선별하여 Queue에 넣기 위해 visited 배열 등을 사용하는데, 이때 visited 배열에는 노드의 위치 값 ((1,2), (5,6) 등)을 저장하게 된다. 하지만 이 문제에서는 문자열을 사용하기 때문에 위치 값을 확인할 수 없었다.

실패 코드

String s = br.readLine();
String t = br.readLine();
int answer = 0;
Queue<String> queue = new LinkedList<>();

queue.offer(s);

while(!queue.isEmpty()) {
	String next = queue.poll();

	//queue에서 꺼낸 문자와 t가 같으면 프로그램 종료
	if(next.length() == t.length()) {
		if (next.equals(t)) {
			answer = 1;
			break;
		}

	 //queue에서 꺼낸 문자열 길이가 t보다 길면 프로그램 종료
	} else if (next.length() > t.length()) {
		break;
	} else {

		//1) 문자열 뒤에 A 추가
		StringBuilder sb = new StringBuilder(next);
		sb.append("A");
		queue.offer(sb.toString());

		//2) 문자열 뒤집고 뒤에 B 추가
		sb = new StringBuilder(next);
		sb.reverse().append("B");
		queue.offer(sb.toString());
	}
}

2. T ==> S 연산

---

힌트를 통해 문자열 S에서 T가 아닌, 문자열 T에서 S를 만들 수 있는지를 확인하는 방법을 알아냈다.

대부분 이 방법을 사용하는 이유는 다음과 같다.

1. 해당 문제에서는 보통의 BFS 문제 풀이 방법처럼 중복을 확인할 수 있는 visited 배열을 사용할 수 없다.

2. 중복을 확인할 수 없으니 모든 노드를 Queue에 넣게 되고, 이로 인해 메모리 초과가 발생한다.

3. 따라서 문제를 반대로 생각하여 문자열 T를 S로 연산함으로써 n번만에 문제를 해결하도록 한다.

최종 코드

String s = br.readLine();
StringBuilder t = new StringBuilder(br.readLine());

while(s.length() < t.toString().length()) {
	//마지막 문자가 A면 삭제, B면 삭제 후 뒤집음
	if(t.charAt(t.length() - 1) == 'A') {
		t.deleteCharAt(t.length() - 1);
	} else {
		t.deleteCharAt(t.length() - 1);
		t.reverse();
	}
}

if (s.equals(t.toString())) {
	System.out.print(1);
} else {
	System.out.print(0);
}