[백준 1987] 알파벳 (C++, Java)

www.acmicpc.net/problem/1987

1987번: 알파벳

 

 

문제해설

• DFS 로 문제풀이 
• DFS 로 순회하면서 다른 문자가 나타나면 Count++
• 4 방향 다 돌고 같은 문자 만날시 나와주면서 Count--; 방문 취소 처리 재귀

 

SOL

C++

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

bool visit[26];
int n, m;
char arr[25][25];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
int answer = 0;
 
void dfs(int cnt, int ii, int jj)
{
	answer = max(answer, cnt);

	 
	for (int w = 0; w < 4; w++)
	{
		int nx = ii + dx[w];
		int ny = jj + dy[w];

		if (nx < 0 || ny < 0 || nx>=n || ny >=m )
		{
			continue;
		}
		if (visit[arr[ii][jj] - 'A'] == false)
		{  
			visit[arr[ii][jj] - 'A'] = true;
			dfs(cnt + 1, nx, ny);
			visit[arr[ii][jj] - 'A'] = false;

		}
	}

	 
}
void input()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string temp;
		cin >> temp;

		for (int j = 0; j < m; j++)
		{
			arr[i][j] = temp[j];
		}
	}
}
int main()
{
 
	input();
	dfs(0, 0, 0);
	cout << answer << endl;
	return 0;
}

 

Java

package Z_ShinHanCard_Prepare;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class 백준1987_알파벳_DFSBFS 
{
	static int R;
	static int C;
	static int dir_x[]= {-1,1,0,0};
	static int dir_y[]= {0,0,-1,1};
	static char map[][];
	static int visited[][];
	static String str= "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	static int alpha[]= new int[str.length()];
	static int count=1;
	static int answer=1;
	public static void search (int x, int y) {
		char curr=map[x][y];
		
		
		alpha[str.indexOf(curr)]=1;
		for (int i=0; i<4; i++) {
			int next_x=x+dir_x[i];
			int next_y= y+dir_y[i];
			
			if (next_x<0 || next_x>=R ||next_y<0 || next_y>=C) continue;
			int temp= map[next_x][next_y];
			int temp2 = str.indexOf(temp);
			if (alpha[str.indexOf(temp)]==1) continue;
			count++;
			answer= Math.max(answer, count);
			search(next_x, next_y);
			
		}
		count--;
		alpha[str.indexOf(curr)]=0;
	}
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		String input= br.readLine();
		StringTokenizer st= new StringTokenizer(input);
		R= Integer.parseInt(st.nextToken());
		C= Integer.parseInt(st.nextToken());
		map= new char [R][C];
		visited= new int [R][C];
		Arrays.fill(alpha, 0);
		for (int arr[]: visited) {
			Arrays.fill(arr, 0);
		}
		
		for (int i=0; i<R; i++) {
			input= br.readLine();
			for (int j=0; j<C; j++) {
				map[i][j]= input.charAt(j);
			}
		}
		search(0,0);
		System.out.println(answer);
		
	}

}