«   2022/08   »
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
Archives
Today
15
Total
93,052
관리 메뉴

차근차근

[백준 1987] 알파벳 본문

대학교/Algorithm

[백준 1987] 알파벳

SWKo 2020. 3. 23. 12:21

0. 제목

  • 백준 1987 알파벳
  • BOJ 1987 알파벳
  • C++ 1987 알파벳

1. 문제

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


2. 풀이

  • DFS와 백트래킹을 사용하는 문제이다.
  • 방문 여부를 체크할 때 A~Z, 총 26개의 인덱스를 가진다.
  • 상하좌우 이동하며, 방문하지 않았다면 true로 체크한다.
  • 방문한적이 있다면 무시하고 넘어간다.
  • 가장 깊게 들어간 최댓값이 정답이다.

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
char arr[21][21];
bool visitedAlpha[26];//A~Z
int R, C;
 
int dx[4= {0,1,0,-1};
int dy[4= {1,0,-1,0};
 
int dfs(int x, int y, int check){
    visitedAlpha[check-'A'= true;
    
    int cnt = 0;
    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) continue;
        
        int next = arr[nx][ny];
        if(!visitedAlpha[next-'A']){
            visitedAlpha[next-'A'= true;
            cnt = max(cnt, dfs(nx, ny, next));
            visitedAlpha[next-'A'= false;
        }
    }
    return cnt + 1;
}
 
int main(int argc, const char * argv[]) {
    cin >> R >> C;
    
    for(int i = 0; i < R; i++){
        string s;
        cin >> s;
        for(int j = 0; j < s.length(); j++){
            arr[i][j] = s[j];
        }
    }
   
    cout << dfs(00, arr[0][0]) << '\n';
    
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 10825] 국영수  (0) 2020.04.04
[백준 1182] 부분수열의 합  (0) 2020.03.24
[백준 1987] 알파벳  (0) 2020.03.23
[백준 1759] 암호 만들기  (0) 2020.03.22
[백준 1525] 퍼즐  (0) 2020.03.20
[백준 1697] 숨바꼭질  (0) 2020.03.19
0 Comments
댓글쓰기 폼