(코딩테스트) 백준-1987번 효율적인해킹(DFS)

1) 문제 

 

문제

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

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

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

입력

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

출력

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

 

예제 입력 1

2 4
CAAB
ADCB

예제 출력 1 

3

 

2) 풀이

2.1)  입력조건

- 시간복잡도는 3^26으로 1억 초과?

- 하지만 탐색 방법이 전형적인 dfs로 문제 풀이 

2.2)  풀이과정 

- 재귀함수작성

- 방문한 점의 알파벳이 벡터에 있으면 cnt계산 후 리턴

- 틀렸다

2.3)  코드

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

int r, c, visited[25][25], dist;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
char a[25][25];
vector<char> v;

void go(int y, int x, int cnt)
{
    if (find(v.begin(), v.end(), a[y][x]) != v.end()) {
        dist = max(dist, cnt);
        return;
    }
    visited[y][x] = 1;
    v.push_back(a[y][x]);
    cnt++;
    for (char i : v) cout << i << " ";
    cout << '\n';
    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 || visited[ny][nx])
            continue;

        go(ny, nx, cnt);
    }
    visited[y][x] = 0;
    v.pop_back();
    return;
}

int main()
{
    cin >> r >> c;
    for (int I = 0; I < r; I++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> a[I][j];
        }
    }
    int cnt = 0; // 처음 호출 시 cnt는 0으로 설정
    go(0, 0, cnt);
    cout << dist;
    return 0;
}

3) 해설

3.1)  조건

-방문한 배열을 1차원 배열로 생각해서 문제 접근 필요

3.2)  사용된 알고리즘

 void go(int y, int x, int cnt)
 {
     if (find(v.begin(), v.end(), a[y][x]) != v.end()) {
         dist = max(dist,cnt);
         return;
     }
     visited[y][x] = 1;
     v.push_back(a[y][x]);
     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 || visited[ny][nx])
             continue;
         
         go(ny, nx, cnt);
     }
     visited[y][x] = 0;
     v.pop_back();
     return;
 }

 

3.3)  완성된 코드

- int형을 return 값으로 가지는 dfs

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

int r, c, visited[25][25], dist;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
char a[25][25];
vector<char> v;

 void go(int y, int x, int cnt)
 {
     if (find(v.begin(), v.end(), a[y][x]) != v.end()) {
         dist = max(dist,cnt);
         return;
     }
     visited[y][x] = 1;
     v.push_back(a[y][x]);
     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 || visited[ny][nx])
             continue;
         
         go(ny, nx, cnt);
     }
     visited[y][x] = 0;
     v.pop_back();
     return;
 }

int main()
{
    cin >> r >> c;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> a[i][j];
        }
    }
    int cnt = 0;
    go(0, 0, cnt);
    cout << dist;
    return 0;
}

 

4) 한줄평

- 2차원 배열이라고 해서 방문 배열도 2차원 일 필요 없다

- 알파벳은 선형적이니까

- 재귀함수라고 해서 반드시 종결 조건이 필요한건 아니다.(쫄지마)

- dfs의 경우는 언젠가는 자동으로 종결이 되니까