[BOJ / 백준] 백준 1987번 문제를 풀어보았다. (ft. Java)

2021년 7월 24일 토요일 - 매미가 운다 맴맴

오늘 올려볼 문제는 1987번 알파벳 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘은 저번에 풀었던 문제와 비슷한 문제를 가지고 왔다!

사실 거의 똑같다

입력 예제

입력 예제를 보면 문제가 무슨 말인지 이해하기 쉬울 것이다!

---

풀이 및 코드

문제를 요약하자면 한 번 밟았던 알파벳은 밟지 않고 상하좌우로 움직일 때 가장 많이 갈 수 있는 칸의 개수를 구하는 것이다.

그렇다면 생각해야 할 부분은 좌표의 방문 여부가 아닌 알파벳의 방문 여부가 된다.

각 알파벳은 char형으로 볼 수 있고, char형은 int형으로 볼 수 있으므로 알파벳을 숫자로 생각해서 문제를 풀어보자!

풀이코드

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

public class Main {

    // 알파벳을 숫자로 사용할 것이기 때문에 방문 여부를 확인 하는 배열을 선언했다. (알파벳으로(숫자로) 편하게 배열 접근 가능!)
    static boolean[] visit;
    // 알파벳을 숫자로 바꾸어 저장할 2차원 배열이다.
    static int[][] arr;

    // 입력받은 판의 크기를 저장할 변수와 결과 변수
    static int r, c, result = 0;

    // 상하좌우를 나타내는 배열이다.
    static int[] ra = {0, 1, 0, -1};
    static int[] ca = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input_nums = br.readLine().split(" ");

        r = Integer.parseInt(input_nums[0]);
        c = Integer.parseInt(input_nums[1]);

        arr = new int[r][c];

        visit = new boolean[30];

        for(int i = 0; i < r; i++)
        {
            String input = br.readLine();

            for(int j = 0; j < c; j++)
            {
                arr[i][j] = (int)(input.charAt(j) - 'A');
            }
        }

        solve(0, 0, 1);

        bw.write(result + "\n");
        bw.flush();
    }

    // 해당 좌표와 지나간 칸의 개수를 파라매터로 받는 함수
    public static void solve(int x, int y, int length)
    {
        // 지나간 칸의 개수가 결과값보다 크면 결과값은 지나간 칸의 개수로 바꾼다.
        if(result < length)
            result = length;

        // 해당 좌표에 해당하는 알파벳(숫자)을 방문한 것으로 만든다.
        visit[arr[y][x]] = true;

        // 상하좌우 좌표에 대해서 방문하지 않은 알파벳이고 판의 크기보다 크거나 작지 않다면
        for(int i = 0; i < 4; i++)
        {
            if(x + ca[i] < c && x + ca[i] >= 0 && y + ra[i] < r && y + ra[i] >= 0)
            {
                if(!visit[arr[y + ra[i]][x + ca[i]]])
                {
                    // 재귀를 진행한다.
                    solve(x + ca[i], y + ra[i], length + 1);
                }
            }
        }

        visit[arr[y][x]] = false;
    }

}

---

제출 화면

알파벳을 숫자로 바꾸어서 생각한다면 저번에 풀었던 1103번 게임 과 매우 유사한 문제였다.

오늘도 이 포스팅이 누군가에게 도움이 되길바란다.

'백준 문제 풀이' 카테고리의 다른 글

[BOJ / 백준] 백준 17298번 문제를 풀어보았다. (ft. Java)  (0)	2021.07.30
[BOJ / 백준] 백준 1043번 문제를 풀어보았다. (ft. Java)  (0)	2021.07.26
[BOJ / 백준] 백준 2578번 문제를 풀어보았다. (ft. Java)  (0)	2021.07.21
[BOJ / 백준] 백준 2243번 문제를 풀어보았다. (ft. Java)  (0)	2021.07.16
[BOJ / 백준] 백준 15904번 문제를 풀어보았다. (ft. Java)  (0)	2021.07.16