[BOJ] 23085. 판치기 -Java

📝 문제

문제 | 백준 23085. 판치기

💡 풀이 과정

⛓ 사용한 알고리즘 : BFS

BFS 탐색을 진행하며 문제에 제시된 조건을 잘 체크하면 쉽게 풀리는 문제이다.

그래프로 생각하기

처음엔 DP로 풀어야 한다고 생각했다. 그런데 생각해보니 K-뒤집기를 사용했을 때 뒤집어지는 동전의 위치에 대한 제약이 없고(예를 들어 HHHHH 를 K=3으로 뒤집는다고 생각하면 HHTTT 와 TTTHH 는 같은 경우가 되겠죠), 어떤 경우에서든 H와 T의 개수의 총합은 N으로 동일하다. 따라서 같은 문자열로 판단되는 문자열의 중복 개수를 줄이는 방식을 생각하게 되었고, 각 문자를 문자열 속에 있는 문자가 아닌 그래프 안의 노드로 생각할 수 있겠다는 아이디어가 떠올랐다.

현재 뒤집어진 상태를 노드에 저장하고, 모두 뒷면으로 뒤집어진 상태의 노드까지 가는 최단 거리를 구하는 방식으로 풀 수 있지 않을까? 라는 생각이 들었고, N 의 크기가 3,000 이하로 크지 않기 때문에 BFS로도 충분히 풀 수 있을 것 같았다. 앞서 고민했던 중복 체크는 방문체크를 해준다면 충분히 해결 가능한 문제라고 생각했다.

조건에 맞게 구현하기

1. 필요한 정보 선정

   우선 BFS로 풀어야 하기 때문에 Queue에 무엇을 저장해야 할지를 생각해야한다. 앞서 떠올린 아이디어로는 현재 뒤집어진 상태인데, 우리가 원하는 것은 모두 뒤집어진 상태이므로 사실상 뒷면의 개수만 저장해도 된다(앞면의 개수는 N-뒷면의 개수 가 되겠네요). 그럼 굳이 문자열을 비교할 필요 없이 뒷면의 개수 = N 이면 모두 뒤집어진 상태라고 판단할 수 있다. 추가적으로 최단거리를 구해야 하기 때문에 현재 depth를 저장해둬야 한다. 두 숫자를 저장해야 해서 Node 클래스를 새로 만들까 하다가 그냥 int 배열을 사용해서 Queue에 저장하기로 했다(굳이 클래스를 만드는 게 귀찮아서).

   정리해보면 필요한 정보는 다음과 같다.

   • 뒷면의 개수
   • 현재 depth

2. 체크해줘야 할 것

   BFS의 while 문 안에서 체크해줘야 할 조건은 다음과 같다.

   • 뒷면의 개수가 N과 동일한가?
     • 이 경우에는 현재 depth를 반환한다. 원하는 최종 목적지 노드에 도달했기 때문이다.
   • K번 반복문을 돌면서 큐에 노드를 넣을 때, 뒤집기로 뒤집어질 뒷면의 개수는 현재 뒷면의 개수보다 클 수 없고, 마찬가지로 뒤집기로 뒤집어질 앞면의 개수는 현재 앞면의 개수보다 클 수 없다.
     • 이러한 경우는 고려할 필요가 없으므로 큐에 넣지 않고 패스한다.
   • 이미 체크한 상황일 경우
     • 앞서 HHTTT 와 TTTHH 는 동일한 상황이기 때문에 방문체크를 해주고 해당 노드를 이미 방문한 경우는 패스한다(최단거리가 아니기 때문).

3. BFS 함수화

   뒷면이 N이 되게 뒤집지 못하는 상황에서는 -1 을 출력해야 한다. 따라서 간단한 BFS지만 main 함수에 넣지 않고 BFS 자체를 함수화해서 정답인 경우에는 정답을, 큐를 모두 비워서 루프를 탈출한 경우에는 -1 을 리턴하도록 구현했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int K;
	
	static int bfs(int T) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[]{T, 0});
		boolean[] visit = new boolean[N+1];
		visit[T] = true;
		
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			int t = temp[0];
			int cnt = temp[1];
			int h = N-t;
			
			if(t==N) return cnt;
			
			for(int i=0;i<=K;i++) {
				int tmpb = i;
				int tmpf = K-i;
				
				if(tmpb>t || tmpf>h) continue;
				
				if(visit[t-tmpb+tmpf]) continue;
				
				visit[t-tmpb+tmpf] = true;
				q.add(new int[] {t-tmpb+tmpf, cnt+1});
			}
		}
		
		return -1;
		
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		char[] coins = br.readLine().toCharArray();
		
		int T=0;
		for(char c: coins) {
			if(c=='T')
				T++;
		}
		
		if(T==N)
			System.out.println(0);
		else {
			System.out.println(bfs(T));
		}
		
	}
}