Baekjoon/[6] 백트래킹

[백준] 1987번 알파벳 JAVA (자바) 풀이

Poorm 푸름 2024. 8. 6. 20:40

문제 1967번 (백트래킹)

 

 :  세로 칸, 가로 칸으로 된 표 모양의 보드

    각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다

    말은 상하좌우로 이동 가능

    새로 이동한 칸의 알파벳 ≠ 지금까지 지나온 모든 칸에 적혀 있는 알파벳

    (즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다)

    좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구해라 (좌측 상단의 칸 포함)

 

 

 [입력]


 :  첫째 줄에 과 가 빈칸을 사이에 두고 주어진다 ()

 :  둘째 줄부터 개의 줄에 걸쳐서 보드에 적혀 있는 개의 대문자 알파벳

 

 

 [출력]


 :  첫째 줄에 트리의 지름을 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 

 

 

 1. 중복되지 않는 알파벳 비교는 visit 배열 사용하기

  • 처음엔 리스트에 지금까지 거쳐왔던 알파벳을 리스트에 넣어 하나씩 비교해볼 생각이였지만
    visit 배열을 이용하면 더욱 간편하다
  • visit이 true라면 중복되는 알파벳이기 때문에 종료하고 최대 카운트를 출력한다
  • visit이 false라면 visit 처리하고 그때그때 max값을 갱신하고 다음 깊은 dfs를 실행한다

 2. visit의 index는 문자가 될 수 없다

  • 애초에 입력을 char형으로 받았으므로 visit[arr[x][y]]는 문자가 된다
  • 인덱스는 정수형으로 받아야 하기 때문에 arr[x][y] - 'A'로 변경한다

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N;
    static int max = 0;
    static boolean visit[];
    static ArrayList<int []> tree[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new ArrayList[N+1];
        
        
        for(int i=1;i<=N;i++){
            tree[i] = new ArrayList<>();
        }
        
        for(int i=0;i<N-1;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            
            tree[p].add(new int[]{c,w});
            tree[c].add(new int[]{p,w});
        }
        
        for(int i=1;i<tree.length;i++){
            visit = new boolean[N+1];
            dfs(i,0);
        }
        System.out.println(max);
    }
    
    static void dfs(int node, int distance){
        visit[node] = true;
        max = Math.max(distance,max);
        
        for(int[] t:tree[node]){
            if(!visit[t[0]]){
                dfs(t[0], distance+t[1]);
            }
        }
    }
}

 

 [해설]
     

 :  static int R, C;
    static int max = 0;
    static char[][] arr;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static boolean[] visit;

 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    R = Integer.parseInt(st.nextToken());  입력1
    C = Integer.parseInt(st.nextToken());  입력2
    arr = new char[R][C];  문자 담기
    visit = new boolean[26];  A-Z 알파벳 방문 여부를 체크

 :  for (int i = 0; i < R; i++) {  arr에 알파벳 문자 저장
            arr[i] = br.readLine().toCharArray();
    }

 :  dfs(0, 0, 1);  초기 count를 1로 시작
    System.out.println(max);  max 결과 출력
    

 :  static void dfs(int x, int y, int count) {
        int index = arr[x][y] - 'A';  인덱스에 들어갈 문자 정수로 바꾸기
        if (visit[index]) {  중복되는 알파벳 발견하면 종료
            return;
        }

        visit[index] = true;  방문처리
        max = Math.max(max, count);  방문한 후 max 갱신
        for (int i = 0; i < 4; i++) {  상하좌우 탐색
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < R && ny >= 0 && ny < C) {  다음 좌표가 범위 안에 있다면
                dfs(nx, ny, count + 1);  더 깊이 다음 전진할 dfs 실행
            }
        }
        visit[index] = false;  백트래킹
    }


  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

https://www.acmicpc.net/problem/1987

 

 

 

 


* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

저작자표시