[Baekjoon] 32076_Easy as ABC

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

---

< Easy as ABC >

 

문제 풀이 

 

사전적으로 가장 앞에 있는 가장 작은 길이의 단어를 찾기 위해서는 단어 시작이 A, B, C 순이어야 한다. 만약 3x3 그리드 내에 A가 있다면 무조건 A로 시작해야 사전적으로 가장 앞에 있는 단어를 만들 수 있기 때문이다. A가 없다면 B로 시작하고, B가 없다면 C로 시작해야 한다. 8방향으로 이동하면서 구할 수 있는 단어를 모두 구해 정렬 후 맨 앞에 있는 값이 정답이다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

public class _32076_ { // Easy as ABC

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

		char arr[][] = new char[3][3];

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
		});

		for (int i = 0; i < 3; i++) {
			String str = bf.readLine();
			for (int j = 0; j < 3; j++) {
				arr[i][j] = str.charAt(j);
				queue.add(new int[] { i, j, arr[i][j] - '0' });
			}
		}

		int num = queue.peek()[2];
		int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
		int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
		ArrayList<String> list = new ArrayList<>();

		while (!queue.isEmpty() && num == queue.peek()[2]) {
			int temp[] = queue.poll();
			boolean visited[][] = new boolean[3][3];

			visited[temp[0]][temp[1]] = true;

			for (int i = 0; i < 8; i++) {
				String str = Character.toString((char) (temp[2] + '0'));
				int x = temp[0] + dx[i];
				int y = temp[1] + dy[i];

				if (x >= 0 && x < 3 && y >= 0 && y < 3 && !visited[x][y]) {
					str = str + arr[x][y];
					visited[x][y] = true;
					for (int j = 0; j < 8; j++) {
						int x2 = x + dx[j];
						int y2 = y + dy[j];

						if (x2 >= 0 && x2 < 3 && y2 >= 0 && y2 < 3 && !visited[x2][y2]) {
							String str2 = str + arr[x2][y2];
							list.add(str2);
						}
					}
				}
			}
		}
		Collections.sort(list);
		System.out.println(list.get(0));
	}
}

변수)
arr : 그리드
queue : 우선순위 큐 
num : 시작 값
dx, dy : 이동할 수 있는 8방향
list : 만들 수 있는 단어
visited : 방문 여부

 

배열 arr에 입력받은 값을 저장하며 우선순위 큐에 [위치, 문자]를 저장합니다. 이때, 우선순위 큐는 문자를 기준으로 오름차순으로 우선순위를 가집니다. 우선순위 큐에 A, B, C 순서로 정렬되어 있기 때문에 큐의 peek() 값을 기준으로 일치하는 값을 가진 위치를 기준으로 다음 과정을 반복합니다.

 

1) queue.poll()

2) 8방향으로 이동하여 그리드 범위 내고 아직 방문하지 않은 곳이라면 문자 추가 및 방문 표시

3) 그 위치에서 다시 8방향으로 이동하여 그리드 범위 내고 아직 방문하지 않은 곳이라면 문자 추가 및 ArrayList에 추가

 

최종 ArrayList를 정렬 후 맨 앞에 있는 값을 출력합니다.

---

---