[백준 1987 골드4] 알파벳

www.acmicpc.net/problem/1987

1987번: 알파벳

해결방안

• 백트래킹(Backtracking)을 이용한 방식 사용

알고리즘

1. 변수 초기화
   1. 상하좌우로 움직일 수 있도록 초기화
   2. 알파벳을 딕셔너리를 이용해서 초기화
   3. 현재 알파벳 길이를 나타내는 변수 0으로 초기화
   4. 처음 알파벳은 포함되어야 하므로 함수 수행전에 1 추가시켜 줌
2. 상하좌우 4방향에대해 반복문 수행
3. 범위 안에 있고 그 위치에 있는 알파벳이 현재 존재하지 않을 경우에 로직 수행
4. 알파벳재귀 함수를 이용하여 cnt라는 변수에 변화를 주고 그 값이 최대값이 될 때를 찾는 과정
5. 알파벳이 key로 있는경우 0이라는 value를 가짐
   1. 즉, 알파벳의 value가 0일 경우는 현재 포함되지 않기 때문에, 지나갈 수 있다는 것을 의미
6. 0인 경우 cnt와 알파벳에 해당하는 딕셔너리의 value를 증가시킴으로써 지나간다는 것을 표현
7. 재귀를 수행
   1. 재귀는 계속해서 4방향을 보기 때문에 보드를 벗어나게 되면 자동적으로 종료
   2. 재귀를 수행하며 cnt의 최대값을 구함
8. 재귀를 통해 얻은 cnt의 최대값을 리턴

 

 

핵심 팁

• 백트래킹 문제
• 재귀 함수가 종료되는 부분과 재귀에 들어가고 나올때의 조건을 처리하는 부분이 중요
  • 재귀 함수가 끝나면 들어갔던 부분을 다시 이전상태로 복구 시켜야 함
• 1번째 원소를 추가하고 시작하여야 함
• 파이썬으로 수행할 경우 시간초과 발생
  • BFS로 수행하면 성공 가능
• 자바로 수행할 경우 성공
  • 최적화 필요

자바 코드 (성공)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class problem1987_alphabet {
    public static int[] mx = {-1, 0, 1, 0};
    public static int[] my = {0, 1, 0, -1};
    public static int ans;
    public static int r;
    public static int c;
    // map 보다는 어차피 알파벳이니까 그냥 배열을 사용하는게 편리함
    public static Map<Character, Integer> alphabets;
    public static char[][] maps;
    private static void dfs(int i, int j, int cnt){
        ans = Math.max(ans, cnt);
        for(int k = 0; k < 4; k++){
            int nextX = i + mx[k];
            int nextY = j + my[k];
            if (nextX >= 0 && nextX < r && nextY >= 0 && nextY < c && alphabets.get(maps[nextX][nextY]) == 0){
                alphabets.put(maps[nextX][nextY], alphabets.get(maps[nextX][nextY]) + 1);
                cnt += 1;
                dfs(nextX, nextY, cnt);
                alphabets.put(maps[nextX][nextY], alphabets.get(maps[nextX][nextY]) - 1);
                cnt -= 1;
            }
        }
    }
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        ans = 0;
        maps = new char[r][c];
        alphabets = new HashMap<>();
        for(int i = 0; i < r; i++){
            String t = br.readLine();
            for(int j = 0; j < c; j++){
                maps[i][j] = t.charAt(j);
                if(!alphabets.containsKey(maps[i][j])){
                    alphabets.put(maps[i][j], 0);
                }
            }
        }
        alphabets.put(maps[0][0], alphabets.get(maps[0][0]) + 1);
        dfs(0, 0, 1);
        System.out.println(ans);
    }
}

 

파이썬 코드 (시간 초과)

from collections import defaultdict
r, c = map(int, input().split())
maps = [input() for _ in range(r)]
mv = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ans = 0
alphabets = defaultdict(int)
def dfs(i, j, cnt):
    global ans
    ans = max(ans, cnt)
    for mx, my in mv:
        nx, ny = i + mx, j + my
        if 0 <= nx < r and 0 <= ny < c and alphabets[maps[nx][ny]] == 0:
            alphabets[maps[nx][ny]] += 1
            cnt += 1
            dfs(nx, ny, cnt)
            alphabets[maps[nx][ny]] -= 1
            cnt -= 1
alphabets[maps[0][0]] += 1
dfs(0, 0, 1)
print(ans)

 

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/Algoritm_PS

https://github.com/griffinGC/TIL_Public