<백준 알고리즘> 1987번: 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력 1

2 4 CAAB ADCB

예제 출력 1

3

예제 입력 2

3 6 HFDFFB AJHGDH DGAGEH

예제 출력 2

6

예제 입력 3

5 5 IEFCJ FHFKC FFALF HFGCF HMCHH

예제 출력 3

10

---

Solution

#include<stdio.h>
#include<stdlib.h>

char **board=NULL;
int R, C;

int max_move(int x,int y,int bit)
{
	int move[4]={0, }, max=0;

	for(int i=0;i<26;i++)
		if(bit&1<<i)
			max++;

	if(x>0 && (bit&(1<<(board[x-1][y]-'A')))==0)
		move[0]=max_move(x-1,y,bit|1<<(board[x-1][y]-'A'));
	if(x<R-1 && (bit&(1<<(board[x+1][y]-'A')))==0)
		move[1]=max_move(x+1,y,bit|1<<(board[x+1][y]-'A'));
	if(y>0 && (bit&(1<<(board[x][y-1]-'A')))==0)
		move[2]=max_move(x,y-1,bit|1<<(board[x][y-1]-'A'));
	if(y<C-1 && (bit&(1<<(board[x][y+1]-'A')))==0)
		move[3]=max_move(x,y+1,bit|1<<(board[x][y+1]-'A'));

	for(int i=0;i<4;i++)
		if(move[i]>max)
			max=move[i];

	return max;
}
int main(void)
{
	scanf("%d%d", &R, &C);
	board=(char **)malloc(R*sizeof(char *));
	for(int r=0;r<R;r++)
	{
		getchar();
		board[r]=(char *)calloc(C+1,sizeof(char));

		for(int c=0;c<C;c++)
			scanf("%c", &board[r][c]);
	}

	printf("%d\n", max_move(0,0,1<<(board[0][0]-'A')));
	for(int r=0;r<R;r++)
		free(board[r]);
	free(board);
	return 0;
}

Solution

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static String[] board;
	static int R, C;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		board=new String[R];
		
		for(int i=0;i<R;i++)
			board[i]=br.readLine();
		
		System.out.println(maxMove(0,1<<board[0].charAt(0)-'A'));
	}
	
	static int maxMove(int index,int bit) {
		int[] move=new int[4];
		int x=index/100, y=index%100, max=0;
		
		for(int i=0;i<26;i++)
			if((bit&1<<i)!=0)
				max++;
		
		if(x>0 && (bit&(1<<board[x-1].charAt(y)-'A'))==0)
			move[0]=maxMove(100*(x-1)+y,bit|1<<(board[x-1].charAt(y)-'A'));
		if(x<R-1 && (bit&(1<<board[x+1].charAt(y)-'A'))==0)
			move[1]=maxMove(100*(x+1)+y,bit|1<<(board[x+1].charAt(y)-'A'));
		if(y>0 && (bit&(1<<board[x].charAt(y-1)-'A'))==0)
			move[2]=maxMove(100*(x)+y-1,bit|1<<(board[x].charAt(y-1)-'A'));
		if(y<C-1 && (bit&(1<<board[x].charAt(y+1)-'A'))==0)
			move[3]=maxMove(100*(x)+y+1,bit|1<<(board[x].charAt(y+1)-'A'));
		
		for(int i=0;i<4;i++)
			max=Integer.max(max, move[i]);

		return max;
	}
}