BOJ::1987 알파벳

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


백트래킹을 통해 (1,1) 에서 시작해 최대 몇칸을 움직일 수 있는지 찾는 문제이다.

굳이 visited배열을 통해 방문 여부를 확인 할 필요는 없다.


<JAVA>


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    
    static int r,c,cnt=0,max=0,ax,ay;
    static int dx[]={1,-1,0,0};
    static int dy[]={0,0,1,-1};
    static int map[][]=new int[21][21];
    static boolean check[]=new boolean[26];
    
    public static void main(String args[]) throws NumberFormatException, 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());
        
        for(int i = 1 ; i <= r ; i++){
            String s = br.readLine();
            for(int j = 1 ; j<= c ; j++){
                map[i][j]=s.charAt(j-1)-'A';
            }
        }
        
        dfs(1,1);
        System.out.println(max);
    }
    //백트래킹
    public static void dfs(int a, int b){
        cnt++;
        if(max<cnt){
            max = cnt;
        }
        //방문한 알파벳 체크 
        check[map[a][b]]=true;
        
        for(int i = 0 ; i < 4 ; i++){
            ax = a+dx[i];
            ay = b+dy[i];
            if(ax>0&&ay>0&&ax<=r&&ay<=c){
                if(!check[map[ax][ay]]){
                    dfs(ax,ay);
                }
            }
        }
        
        //탐색 끝났으면 카운트감소/알파벳체크해제
        cnt--;
        check[map[a][b]]=false;
    }
}
cs


<C++>


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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <string>
using namespace std;
 
int r, c, ax, ay, res = 0, cnt = 0;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int map[21][21];
bool check[26];
 
void dfs(int a, int b) {
    cnt++;
    if (res < cnt) {
        res = cnt;
    }
    check[map[a][b]] = true;
 
    for (int i = 0; i < 4; i++) {
        ax = a + dx[i];
        ay = b + dy[i];
        if (ax > 0 && ay > 0 && ax <= r && ay <= c) {
            if (!check[map[ax][ay]]) {
                dfs(ax, ay);
            }
        }
    }
 
    cnt--;
    check[map[a][b]] = false;
}
 
int main() {
    cin >> r >> c;
 
    for (int i = 1; i <= r; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= c; j++) {
            map[i][j] = s.at(j - 1) - 'A';
        }
    }
    dfs(1, 1);
    cout << res << endl;
}
cs


저작자표시

'BOJ::문제풀이' 카테고리의 다른 글

2156 포도주 시식  (0) 2018.01.01
2096 내려가기  (0) 2018.01.01
1965 상자넣기  (0) 2018.01.01
1934 최소공배수  (0) 2018.01.01
1932 숫자삼각형  (0) 2018.01.01

+ Recent posts

티스토리툴바