[SWEA] 2105. 디저트 카페
문제 접근
-
DFS 문제이다.
-
대각선 방향으로 이동하며 해당 위치에 있는 디저트 번호를 확인한 뒤 방향을 바꾸거나 계속해서 같은 방향으로 가며 번호를 확인하는 과정을 반복한다.
이때 동일한 디저트 번호는 방문할 수 없는데, is_visit 배열을 이용하여 이를 구현하였다. -
디저트 카페 투어는 총 4번 방향을 바꿔 출발한 곳으로 돌아와야만 정상적으로 완료된다. 이 부분이 문제의 핵심이다.
dfs함수의 인자로 방향을 나타내는 dir를 주고 이 방향이 마지막 방향을 나타내고, 현재 위치가 출발지점과 동일하면 탐색을 종료하게 했다. -
방향 전환은 총 2가지 종류가 가능하다.
현재 위치에서 두 가지 방향으로 모두 이동해 보면서 정답을 찾도록 했다.
dfs 함수를 서로 다른 인자를 주어 두 번 호출하는 부분이 존재하는 이유이다.
풀이
#include <iostream>
#include <algorithm>
using namespace std;
int T, N, rst, sx, sy;
int map[21][21];
int is_visit[101];
int dy[] = { 1, -1, -1, 1 };
int dx[] = { 1, 1, -1, -1 };
int is_range(int x, int y) {
if (x >= 1 && x <= N && y >= 1 && y <= N) return true;
return false;
}
void dfs(int x, int y, int dir, int cnt) {
if (dir == 3 && sx == x && sy == y) {
rst = max(rst, cnt);
return;
}
if (!is_range(x, y) || is_visit[map[x][y]]) return;
is_visit[map[x][y]] = 1;
dfs(x + dx[dir], y + dy[dir], dir, cnt + 1);
dfs(x + dx[dir + 1], y + dy[dir + 1], dir + 1, cnt + 1);
is_visit[map[x][y]] = 0;
}
void slove() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
sx = i;
sy = j;
dfs(i, j, 0, 0);
}
}
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> map[i][j];
}
}
rst = -1;
}
int main() {
cin >> T;
for (int tc = 0; tc < T; tc++) {
input();
slove();
cout << "#" << tc + 1 << " " << rst << endl;
}
}
Author And Source
이 문제에 관하여([SWEA] 2105. 디저트 카페), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kyoung99u/SWEA-디저트-카페저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)