[Baekjoon] 12026_BOJ 거리

Silver I

문제(출처: https://www.acmicpc.net/problem/12026)

---

< BOJ 거리 >

 

문제 풀이 

 

이중 for문을 사용하여 보도블록을 전체 탐색한다. B -> O -> J 순서로 확인하면서 최솟값을 찾는다.

 

 my solution (Java)

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

public class _12026_ { // BOJ 거리

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());

		char arr[] = new char[n];
		String str = bf.readLine();
		for (int i = 0; i < str.length(); i++) {
			arr[i] = str.charAt(i);
		}

		int result[] = new int[n];

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (result[i] != 0 || i == 0) {
					if ((arr[i] == 'B' && arr[j] == 'O') || (arr[i] == 'O' && arr[j] == 'J')
							|| (arr[i] == 'J' && arr[j] == 'B')) {
						if (result[j] == 0 || result[j] > result[i] + ((j - i) * (j - i)))
							result[j] = result[i] + ((j - i) * (j - i));
					}
				}
			}
		}

		if (n > 1 && result[n - 1] == 0) {
			System.out.println(-1);
		} else {
			System.out.println(result[n - 1]);
		}
	}
}

변수)
n : 보도블록 개수
arr, str : 보도블록 글자
result : 이동하는데 필요한 에너지 양의 최솟값

 

이중 for문을 사용하여 보도블록 전체를 탐색한다. 이미 방문한 곳이거나 스타트라면 다음 이동할 곳을 찾는다. B라면 O인 곳을, O라면 J인 곳을, J라면 B인 곳을 찾은 후 아직 한 번도 방문한 적이 없거나 원래 에너지보다 적은 에너지가 필요하다면 값을 업데이트해 준다.

 

최종 링크 값이 0이라면 스타트가 링크를 만날 수 없는 것이므로 -1을 출력하고 0이 아니라면 링크 값을 출력해 준다.

 

* n이 1일 경우 스타트와 링크가 일치하므로 0을 출력해 준다.

---

---