BEAKJOON / 백준 - JAVA 32076번 Easy as ABC

2024.08.09기준 - 실버4

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 3x3의 격자가 있을 때 자신을 제외한 인접한 모든 단어들을 이용해서 3자리로 된 단어 중 사전순으로 가장 빠른 단어를 출력하는 문제입니다.

 

접근 방법

1. 커스텀 클래스를 생성해 문자열을 저장해주었습니다.
2. 우선순위 큐를 이용해 가장 먼저 3자리 문자열이 만들어지는 것이 사전순으로 가장 빠른 단어이기 때문에 우선순위 큐를 이용했습니다.

1. 커스텀 클래스를 생성했습니다.

// 좌표와 문자열, 방문 표시를 저장하는 커스텀 클래스
private static class Coordinate implements Comparable<Coordinate> {
    int x, y;
    String str;
    boolean[][] visit;

    public Coordinate (int y, int x, boolean[][] v, String s) {
        this.y = y;
        this.x = x;
        str = s;
        visit = v;
    }

    @Override
    public int compareTo(Coordinate o) {
        return str.compareTo(o.str);
    }
}

 

2. 입력받은 그리드 정보를 저장해줍니다.

// 입력받은 그리드 정보를 저장하는 배열
char[][] grid = new char[3][3];
char[] arr;

for (int i = 0; i < 3; i++) {
    arr = br.readLine().toCharArray();

    for (int j = 0; j < 3; j++) {
        grid[i][j] = arr[j];
    }
}

 

3. 문자열 기준으로 정렬을 해주는 우선순위 큐를 생성해주어 우선적으로 모든 칸의 문자를 넣어줍니다.

// 문자열 기준으로 정렬을 해주는 우선순위 큐
PriorityQueue<Coordinate> q = new PriorityQueue<>();
boolean[][] visit;

// 우선적으로 모든 칸을 다 넣어준다.
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        visit = new boolean[3][3];
        visit[i][j] = true;
        q.add(new Coordinate(i, j, visit, String.valueOf(grid[i][j])));
    }
}

커스텀 클래스를 생성할 때, Comparable를 이용해 문자열 기준으로 정렬을 하도록 설정해주었습니다.

 

4. 현재 좌표에서 참조하는 범위를 배열로 생성해 주었습니다.

// 현재 좌표에서 참조하는 좌표 범위
int[] dx = {-1, 0, 1, -1, 1, -1, 0, 1};
int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};

 

5. 우선순위 큐를 이용해 가장 빠르게 완성되는 문자열을 출력해줍니다.

Coordinate cd;
int nexty, nextx;
while (!q.isEmpty()) {
    cd = q.poll();

    // 우선순위 큐로 인해 가장 먼저 3자리가 만들어지는 것이 사전순으로 가장 빠르다.
    if (cd.str.length() == 3) {
        sb.append(cd.str);
        break;
    }

    for (int i = 0; i < 8; i++) {
        nexty = cd.y + dy[i];
        nextx = cd.x + dx[i];

        // 그리드 범위에 존재하면서 방문하지 않은 곳이라면
        if (check(nexty, nextx) && !cd.visit[nexty][nextx]) {
            visit = truecheck(cd.visit);
            q.add(new Coordinate(nexty, nextx, visit, cd.str + grid[nexty][nextx]));
        }
    }
}

 

5-1. 방문을 표시해주는 함수를 따로 생성해 각각의 Coordinate에 방문 처리를 표시해주었습니다.

// 방문을 표시해주는 함수.
private static boolean[][] truecheck(boolean[][] v) {
    boolean[][] visit = new boolean[3][3];

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            visit[i][j] = v[i][j];
        }
    }

    return visit;
}

 

5-2. 그리드 범위를 벗어나는 곳을 참조하면 에러가 뜨기 때문에 그리드 범위에 있는지 체크해주는 함수를 생성합니다.

// 그리드 범위를 체크해주는 함수.
private static boolean check (int y, int x) {
    return 0 <= x && 0 <= y && y < 3 && x < 3;
}

 

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	// 좌표와 문자열, 방문 표시를 저장하는 커스텀 클래스
	private static class Coordinate implements Comparable<Coordinate> {
		int x, y;
		String str;
		boolean[][] visit;
		
		public Coordinate (int y, int x, boolean[][] v, String s) {
			this.y = y;
			this.x = x;
			str = s;
			visit = v;
		}
		
		@Override
		public int compareTo(Coordinate o) {
			return str.compareTo(o.str);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		// 입력받은 그리드 정보를 저장하는 배열
		char[][] grid = new char[3][3];
		char[] arr;
		
		for (int i = 0; i < 3; i++) {
			arr = br.readLine().toCharArray();
			
			for (int j = 0; j < 3; j++) {
				grid[i][j] = arr[j];
			}
		}
		
		// 문자열 기준으로 정렬을 해주는 우선순위 큐
		PriorityQueue<Coordinate> q = new PriorityQueue<>();
		boolean[][] visit;
		
		// 우선적으로 모든 칸을 다 넣어준다.
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				visit = new boolean[3][3];
				visit[i][j] = true;
				q.add(new Coordinate(i, j, visit, String.valueOf(grid[i][j])));
			}
		}
		
		// 현재 좌표에서 참조하는 좌표 범위
		int[] dx = {-1, 0, 1, -1, 1, -1, 0, 1};
		int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};
		
		Coordinate cd;
		int nexty, nextx;
		while (!q.isEmpty()) {
			cd = q.poll();
			
			// 우선순위 큐로 인해 가장 먼저 3자리가 만들어지는 것이 사전순으로 가장 빠르다.
			if (cd.str.length() == 3) {
				sb.append(cd.str);
				break;
			}
			
			for (int i = 0; i < 8; i++) {
				nexty = cd.y + dy[i];
				nextx = cd.x + dx[i];
				
				// 그리드 범위에 존재하면서 방문하지 않은 곳이라면
				if (check(nexty, nextx) && !cd.visit[nexty][nextx]) {
					visit = truecheck(cd.visit);
					q.add(new Coordinate(nexty, nextx, visit, cd.str + grid[nexty][nextx]));
				}
			}
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 방문을 표시해주는 함수.
	private static boolean[][] truecheck(boolean[][] v) {
		boolean[][] visit = new boolean[3][3];
		
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				visit[i][j] = v[i][j];
			}
		}
		
		return visit;
	}
	
	// 그리드 범위를 체크해주는 함수.
	private static boolean check (int y, int x) {
		return 0 <= x && 0 <= y && y < 3 && x < 3;
	}
}