백준 코딩
백준 1987번: 알파벳
까르르꿍꿍
2022. 2. 5. 15:22
https://www.acmicpc.net/problem/1987
1987번: 알파벳
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으
www.acmicpc.net
이 문제는 재귀를 이용해서 풀었는데 알파벳이 중첩이 안되어야하니 알파벳 중첩을 확인할 체크 배열을 두고
움직이는 함수 go에서 왼쪽, 오른쪽,위쪽,아래쪽 총 4번이동할 경우를 재귀적으로 풀었다.
코드를 보는게 쉽다
#include <cstdio>
using namespace std;
char alpa[20][20];
bool check[26];
int r,c;
int max;
void go(int row,int col,int i){ //row는 열 ,col은 행, i는 몇번째 인지
check[alpa[col][row]-'A']=true;
if(max<i){
max=i;
}
if(row-1>=0&&check[alpa[col][row-1]-'A']==false){ //왼쪽으로 이동
go(row-1,col,i+1);
}
if(row+1<c&&check[alpa[col][row+1]-'A']==false){ //오른쪽으로 이동
go(row+1,col,i+1);
}
if(col-1>=0&&check[alpa[col-1][row]-'A']==false){ //위쪽으로 이동
go(row,col-1,i+1);
}
if(col+1<r&&check[alpa[col+1][row]-'A']==false){ //아래쪽으로 이동
go(row,col+1,i+1);
}
check[alpa[col][row]-'A']=false; //다들렸으면 들른 알파벳 빼주기
return;
}
int main(){
scanf("%d %d",&r,&c);
for(int i=0;i<r;i++){
for(int k=0;k<c;k++){
scanf(" %1c",&alpa[i][k]);
}
}
go(0,0,1);
printf("%d",max);
return 0;
}