[백준] 알고리즘 분류(그래프 이론,JAVA)1987번, 알파벳

문제 링크

1987번: 알파벳

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 보드는 R × C칸으로 구성되며, 대문자 알파벳 하나씩 적혀있습니다.

2. 말은 상하좌우로 이동가능하며, 지나는 알파벳은 모두 달라야 합니다.

3. 1행 1열로 시작하여 말의 최대 이동 거리를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 깊이 우선 탐색으로 말이 이동할 수 있는 모든 경우를 탐색합니다.

 

3. 탐색이 종료된 뒤 최대 이동한 거리를 결과로 출력합니다.

 

 

모든 경우 탐색.

 

보드에서 1행 1열을 기준으로 DFS을 진행하여 말이 움직이는 모든 경우를 탐색합니다.

※보드 방문 확인은 알파벳에 따라 구분되도록 하였습니다.

 

예를 들어 아래와 같은 보드 상태일 때

 

A	B	C
A	C	C
F	F	F

 

최대 이동

A(→)	B(↓)	C
A	C(↓)	C
F	F	F

다른 경우

A(→)	B(→)	C
A	C	C
F	F	F

 

DFS 탐색이 종료된 뒤 최대 이동 거리 : 4

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

R = 2

C = 4

 

보드 정보

 

C	A	A	B
A	D	C	B

 

2. 깊이 우선 탐색으로 말이 이동할 수 있는 모든 경우를 탐색합니다.

 

DFS탐색!

 

 

C(→)	A(↓)	A	B
A	D	C	B

이동 거리 : 3

 

C(↓)	A	A	B
A(→)	D	C	B

이동 거리 : 3

 

3. 탐색이 종료된 뒤 최대 이동한 거리를 결과로 출력합니다.

 

최대 이동 거리 : 3

 

3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용하여 R, C를 띄어쓰기 기준으로 나누었습니다.
• dfs함수를 이용하여 말이 이동하는 모든 경우를 탐색합니다.
• 탐색 종료한 뒤 말의 최대 이동 거리를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs함수는 DFS으로 말이 보드에 이동하는 모든 경우를 탐색합니다.
• charOfInt함수는 알파벳을 배열의 Index형태로 변경합니다.
• inSpace함수는 말이 이동하는 칸이 보드에 존재하는지 확인합니다.

 

결과코드

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

public class Main{
    static char[][] board;	//보드 정보 저장 배열
    static boolean[] visited = new boolean[26];	//알파벳 사용 확인 배열
    static int R, C, answer = 0;
    static int[] dy = {-1, 1, 0, 0};	//상하좌우 y변경값
    static int[] dx = {0, 0, -1, 1};	//상하좌우 x변경값
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        board = new char[R][C];
        //보드 정보 저장
        for(int i=0;i<R;i++){
            String str = br.readLine();
            for(int j=0;j<C;j++)
                board[i][j] = str.charAt(j);
        }
        //1행 1열의 알파벳 사용 확인
        visited[charOfInt(board[0][0])] = true;
        dfs(0, 0, 1);	//DFS로 말 이동하는 모든 경우 탐색
        bw.write(answer + "");	//최대 이동 거리 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //DFS탐색으로 말의 이동 모든 경우 탐색 함수
    static void dfs(int x, int y, int count){
        boolean check = false;	//말이 이동하는지 확인 변수
        //말 상하좌우 탐색
        for(int i=0;i<4;i++){
            //상하좌우 x와 y 변경
            int tempX = x + dx[i];
            int tempY = y + dy[i];
            //문제 조건에 만족하도록 말이 이동할 때
            if(inSpace(tempX, tempY) && !visited[charOfInt(board[tempY][tempX])]){
                //이동하는 칸에 알파벳 번호 구하기
                int index = charOfInt(board[tempY][tempX]);
                visited[index] = true;	//알파벳 사용
                dfs(tempX,tempY, count+1);	//다음칸 탐색
                visited[index] = false;	//알파벳 미사용
                check = true;	//말이 이동을 확인
            }
        }
        //말이 이동하지 않았을 때 = 최종 목적지 도착
        if(!check)
            answer = Math.max(answer, count);
    }
    //대문자 알파벳 -> Int형 변경 함수
    static int charOfInt(char c){
        return c - 65;
    }
    //말 이동시 보드안에 존재하는지 확인하는 함수
    static boolean inSpace(int x, int y){
        if(y < R && y>=0 && x<C && x>=0)
            return true;
        return false;
    }
}