[BOJ]1987번 : 알파벳(java, c++)

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

1987번: 알파벳

 

백트랙킹 (java 소스)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.List;
 
public class Main {
    
    static List<Integer> listLotto;
    static List<String> listCompleteLotto;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        // 입력
        String[] NnM = br.readLine().split(" ");
        int R = Integer.parseInt(NnM[0]);
        int C = Integer.parseInt(NnM[1]);
        
        String[] arrBoardLine = new String[R];
        for (int i = 0; i < R; i ++) {
            arrBoardLine[i] = br.readLine();
        }
        
        // 체크 배열 생성 및 첫번째 자리 체크
        boolean[] arrCheck = new boolean[26];
        arrCheck[arrBoardLine[0].charAt(0) - 'A'] = true;
        
        // 재귀함수 실행 및 출력
        bw.write(go(arrBoardLine, arrCheck, 0, 0) + "\n");
        bw.flush();
    }
    
    // 상 하 우 좌
    static int[] directionX = {0, 0, 1, -1};
    static int[] directionY = {1, -1, 0, 0};
    
    private static int go(String[] arrBoardLine, boolean[] arrCheck, int x, int y) {
        
        int ans = 0;
        
        //4 방향
        for (int i = 0; i < 4; i++) {
            
            int nowX = x + directionX[i];
            int nowY = y + directionY[i];
            
            // 현재 위치가 정상이면
            if (nowX >= 0 && nowY >= 0 && nowX < arrBoardLine.length && nowY < arrBoardLine[0].length()) {
                
                int nowPoint = arrBoardLine[nowX].charAt(nowY) - 'A';
                
                // 아직 지나가지 않았으면
                if (arrCheck[nowPoint] == false) {
                    
                    arrCheck[nowPoint] = true;
                    
                    // 다음 함수 실행 및 최대값 저장
                    int nextAns = go(arrBoardLine, arrCheck, nowX, nowY);
                    if (ans < nextAns) {
                        ans = nextAns;
                    }
                    
                    // 원복
                    arrCheck[nowPoint] = false;
                }
            }
        }
        
        return ans + 1;
    }
}

 

 

백트랙킹 (c++ 소스)

#include <iostream>
#include <vector>

using namespace std;

int dr_x[] = {0, 1, 0, -1};
int dr_y[] = {1, 0, -1, 0};

int go(vector<string> &alpha, vector<bool> &visit, int x, int y)
{
	int max_cnt = 1;

	// 4방향 탐색
	for (int i = 0; i < 4; ++i)
	{
		int nx = x + dr_x[i];
		int ny = y + dr_y[i];
		
		// 범위 밖을 벗어나면 continue
		if ((nx < 0 || nx >= alpha.size() || ny < 0 || ny >= alpha[0].size()))
		{
			continue;
		}

		// 다음칸의 알파벳을 방문한적이 없으면
		int idx = alpha[nx][ny] - 'A';
		if (!visit[idx])
		{
			visit[idx] = true;
			
			// 한번 이동할 때마다 이동횟수 + 1 
			int cnt = go(alpha, visit, nx, ny) + 1;

			// 최대값 구하기
			if (max_cnt < cnt)
			{
				max_cnt = cnt;
			}
			
			visit[idx] = false;
		}
	}
	return max_cnt;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int R, C;
	cin >> R >> C;
	vector<string> alpha(R);
	for (int i = 0; i < R; ++i)
	{
		cin >> alpha[i];
	}

	// 알파벳 방문 체크할 bool벡터
	vector<bool> visit(26);
	// 첫번째 위치 방문 체크
	visit[alpha[0][0] - 'A'] = true;

	// 최대로 이동할 수 있는 칸수 출력
	cout << go(alpha, visit, 0, 0);

	return 0;
}

 

 

 

전역변수를 두지 않고도 최대 이동 횟수를 계산할 수 있다!

// 한번 이동할 때마다 이동횟수 + 1 
int cnt = go(alpha, visit, nx, ny) + 1;

// 최대값 구하기
if (max_cnt < cnt)
{
	max_cnt = cnt;
}