[C++] 백준 1987번 : 알파벳

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

 

 

[코드]

#include <iostream>
#include <algorithm>
using namespace std;

int r,c,maxnum= -1;
char word[21][21];
bool visit[21];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};

void solve(int x,int y, int count){
    maxnum = max(maxnum,count);
    
    for(int i=0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx<0 || nx>=r || ny<0 || ny>=c) continue;
        if(visit[word[nx][ny]-'A']) continue;
        
        check = true;
        visit[word[nx][ny]-'A']=true;
        solve(nx,ny,count+1);
        visit[word[nx][ny]-'A']=false;
    }
} 

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>r>>c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>word[i][j];
        }
    }

    visit[word[0][0]-'A']=true;
    solve(0,0,1);

    cout<<maxnum;
    return 0;
}

 

 

 

[접근]

깊이 우선 탐색과 백트래킹을 활용하여 풀었다. 

 

 

처음에는 

    for(int i=0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx>=0 && nx<r && ny>=0 && ny<c){
            if(!visit[word[nx][ny]-'A']){
                visit[word[nx][ny]-'A']=true;
                solve(nx,ny,count+1);
                visit[word[nx][ny]-'A']=false;
            }
        }
    }

경계 검사를 하나의 if 문으로 처리했는데,

좀 더 효율적인 방법이 있을것같아 찾아보았다!

 

 

수정한 코드는 다음과 같다. 

 

    
    for(int i=0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx<0 || nx>=r || ny<0 || ny>=c) continue;
        if(visit[word[nx][ny]-'A']) continue;
        
        check = true;
        visit[word[nx][ny]-'A']=true;
        solve(nx,ny,count+1);
        visit[word[nx][ny]-'A']=false;
    }

 

continue 문을 사용하여 조건이 맞지 않을 경우 반복문을 조기에 종료하는게 불필요한 연산을 줄여 효율성을 높일 수 있었다!