🔒[문제 url]
https://www.acmicpc.net/problem/1987
🔑알고리즘
한 경로를 끝까지 탐색할때마다 최대값을 갱신해주고, 분기점으로 돌아올때마다 이전에 탐색했던 기록을 지워줌(BackTracking)을 반복하며 답을 구한다.
- 어떤 방법으로 탐색하는가?
- 최단경로를 찾는 것이 아닌, 어떤 경로로 가는 것이 가장 많은 칸을 갈 수 있는지를 구해야하기때문에 깊이 우선 탐색(DFS)를 택하였다.
- 경로의 끝에 다다를때마다, 지나온 칸 수의 최대값을 갱신해준다.
- 탐색중 주의할 것은?
- 해당 문제는 백트래킹 요소를 포함한다.
I E F C J // (→ ↓ ← ↑) 순서로 방문한다고 가정 F H F K C
- 위와같은 경로를 탐색할 경우,
I E F C J 를 방문한 후에는 J 밑에 위치한 C를 방문하지 못 하기때문에,
I E F C K 경로로 재탐색 하게된다.
이때, J에 대한 방문 기록은 지워야하므로 해당 지점의 DFS가 종료되는 즉시 방문 기록을 false로 바꿔준다.
🐾부분 코드
void INPUT()
{
//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> r >> c;
for(int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
{
scanf("%1s", &map[i][j]);
}
}<입력 함수>
1. 간혹 이렇게 공백없이 입력이 주어지는 경우에는,scanf("%1s", &map[i][j])위 코드를 이용하여 한 글자씩 대입되도록 구현해준다.
2. 이 문제의 경우, map에 담긴 값이 char이기때문에 종료 문자('\0')를 생각해줘야한다. 따라서 입력값 R, C의 최대값인 20으로 배열의 크기를 지정할 경우 틀릴 것을 명심하자.
3. 또한, C++로 알고리즘을 하는 사람들은 모두 아는ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);위 코드는, c와 cpp의 동기화를 꺼줌으로써 입출력 속도를 높이는 목적이다. 따라서 cin과 scanf를 혼용해야하는 상황에서는 반드시 지워야한다.
void DFS(int x, int y, int cnt)
{
ans = max(ans, cnt);
visited[map[x][y] - 'A'] = true;
for (int i = 0; i < 4; i++)
{
int dx[4] = { 0,0,-1,1 }; // 우 좌 상 하
int dy[4] = { 1,-1,0,0 };
int nx = x + dx[i], ny = y + dy[i];
if (0 <= nx && nx < r && 0 <= ny && ny < c)
{
if (!visited[map[nx][ny] - 'A'])
{
DFS(nx, ny, cnt + 1);
//backTracking
visited[map[nx][ny] - 'A'] = false;
}
}
}
}<DFS 함수>
cnt 변수를 인자로 받음으로써, 한 칸을 지나갈때마다 1씩 추가해준다.
출력 답안이 될 ans변수에 최대값을 갱신해가며 탐색을 진행한다.visited[map[x][y] - 'A'] = true;map은 대문자 알파벳을 값으로 갖기때문에,위 코드와 같이 아스키 코드를 이용하여 visited 배열을 indexing 해준다.
굳이 이 문제가 Gold4가 된 이유는 한 줄이면 해결될 백트래킹 요소때문인듯 하다. 위에서 언급했듯, 다른 경로 탐색에 영향이 없도록 DFS 호출이 끝나면//backTracking visited[map[nx][ny] - 'A'] = false;위 코드를 통해 visited를 갱신해준다.
void SOLVE()
{
DFS(0, 0, 1);
cout << ans;
}<DFS 시작 및 출력>
시작 위치는 좌측 상단으로 고정이므로, 위치 정보를 0 0 으로 넘겨준다.
문제 조건에 따라 좌측 상단또한 건너는 칸에 포함이므로, cnt값은 1 로 넘겨준다.
ans의 갱신은 DFS 함수 내에서 되므로 바로 출력한다.
🪄전체 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stdio.h>
#include <ctime>
#include <memory.h> // memset
#include <numeric>
#include <stack>
#include <sstream>
using namespace std;
int r, c;
char map[21][21]; // \0 에 의해 20으로 잡으면 오답
bool visited[26];
int ans = -1;
void INPUT()
{
//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> r >> c;
for(int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
{
scanf("%1s", &map[i][j]);
}
}
void DFS(int x, int y, int cnt)
{
ans = max(ans, cnt);
visited[map[x][y] - 'A'] = true;
for (int i = 0; i < 4; i++)
{
int dx[4] = { 0,0,-1,1 }; // 우 좌 상 하
int dy[4] = { 1,-1,0,0 };
int nx = x + dx[i], ny = y + dy[i];
if (0 <= nx && nx < r && 0 <= ny && ny < c)
{
if (!visited[map[nx][ny] - 'A'])
{
DFS(nx, ny, cnt + 1);
visited[map[nx][ny] - 'A'] = false;
}
}
}
}
void SOLVE()
{
DFS(0, 0, 1);
cout << ans;
}
int main()
{
INPUT();
SOLVE();
}🥇문제 후기
정말 오랜만에 개념적인 부분을 놓쳐 오답이 나왔던 문제.
char을 입력받을 경우 '\0'를 생각해야한다는 것..!
문제에서 주어진 범위에 딱 맞게 변수를 선언하는 습관이 있었기때문에 다시 한번 캐치한 개념이었다. 그놈의 N과M덕에 백트래킹이 익숙해 꽤나 쉽게 해결한 문제.
