1987번: 알파벳

알파벳 

다국어

한국어   

시간 제한             메모리 제한             제출             정답             맞힌 사람             정답 비율

2 초

256 MB

90428

29494

17883

29.346%

문제

세로 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

 

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

1987번: 알파벳

 

흐름

 

맞은 코드

#include <bits/stdc++.h>
using namespace std;

const int MAX = 20;
int r,c, visited[24][24], result=-1, cnt;
char a[24][24];
int alp[26];
const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};

void dfs(int y, int x){
    visited[y][x]=1;
    alp[a[y][x]-'A']=1; cnt++;
    for(int i=0;i<4;i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny>=r || nx>=c || ny<0||nx<0||visited[ny][nx]) continue;
        if(alp[a[ny][nx]-'A']==1) continue;
        dfs(ny,nx);
        result = max(result, cnt);
        //초기화
        cnt--; alp[a[ny][nx]-'A']=0; 
        visited[ny][nx]=0;
    }
    return;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력하기
    cin >> r >> c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin >> a[i][j]; 
        }
    }
    //2. dfs수행
    dfs(0,0);
    //3. 정답 출력
    cout << (result==-1?1:result) <<"\n";

}

 

유의할 점

• 처음엔 알파벳을 세트(set)로 입력받아서 find 함수로 알파벳의 존재여부를 확인하였는데 시간초과가 났다. 그래서 알파벳 배열을 사용하였는데,  int alph[26]를 만들어서 사용하면 1로 표시하였더니 시간초과가 나지 않았다.
  • set는 원소를 찾는 경우(find) O(logN)이 걸리고, 배열은 O(N)이 걸린다.
  • set는 원소를 삽입할 경우 O(logN)이 걸리고, 배열의 경우, 삽입 위치를 안다면 O(1) 상수시간이, 위치를 모른다면 해당 인덱스를 찾아야하므로 검색의 시간인 O(N)이 걸린다.
  • 배열의 원소 접근 시간복잡도는 O(1) 상수시간이 걸린다.
  • 즉, set는 원소를 찾을때, 배열은 원소 인덱스를 사용한 접근, 삽입시 사용한다.
  • 이 문제에서는 알파벳이 사용되었는지 확인하는 문제이므로
    • 1. 알파벳을 저장하고 find한다.-set에 저장하고 find => O(logN)
    • 2. 알파벳을 0부터 시작하는 숫자로 대응하여 배열의 해당 위치에 저장하고 인덱스로 접근한다 => O(1)
    • 당연히 O(1) 상수시간이 빠르므로 배열을 이용하면 시간복잡도가 작다.
• 89%쯤에서 틀려서 질문게시판을 살펴봤더니 반례에서 처음부터 움직이지 못하는 경우가 있었다. 나같은 경우에는 result의 기본값인 -1이 출력되지만 답은 1(시작칸)이므로 반례처리를 꼼꼼하게 해야겠다고 생각했다. 
  • https://www.acmicpc.net/board/view/111288

글 읽기 - 89퍼 언저리 반례

 

사실 비트마스킹으로 풀어보려고했는데(r과 c가 최대 20이므로) 감이 오지 않았다.

선생님은 비트마스킹으로 풀었다.

 

선생님 코드 흐름 - 비트마스킹

 

선생님 코드 - 비트마스킹

#include <bits/stdc++.h>
using namespace std;

int R,C, ret;
char a[24][24];
const int dy[]={-1,0,1,0};
const int dx[]={0,1,0,-1};

void go(int y, int x, int num, int cnt){
    ret = max(ret, cnt);
    for(int i=0;i<4;i++){
        int ny = y+dy[i];
        int nx = x+dx[i];
        if(ny<0||nx<0||ny>=R||nx>=C) continue;
        int next = (1<<(int)(a[ny][nx]-'A')); //알파벳 숫자
        if((num & next)==0){ //경로 존재하는지 확인
            go(ny,nx,num|next,cnt+1);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> R >> C;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            cin >> a[i][j];
        }
    }
    //2. dfs 수행
    go(0,0,1<<(int)(a[0][0]-'A'),1);
    //3. 정답 출력하기
    cout << ret <<"\n";
    return 0;
}