알고리즘/SWEA
SWEA 모의 2105 디저트 카페
- -
SWEA 모의 2105 디저트 카페
문제링크
http://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.
핵심 컨셉
[고려사항]
디저트 카페를 돌아다니며 디저트를 먹는데 이동 방향을 대각선이다.
이동 시 주의 사항이 여러가지 존재하는데
1. 어느 한 카페에서 출발한다 -- 어딘지 특정할 수 없기 때문에 모든 점에서 탐색 해볼 필요가 있다.
2. 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
3. 왔던 길을 다시 되돌아 갈 수 없다.
-- 2, 3의 조건에 의해 회전을 해서 출발지로 돌아와야 함을 알 수 있다.
-- 어차피 회전해서 돌아오기 때문에 오른쪽 또는 왼쪽을 모두 고민할 필요가 없다. 우리는 오른쪽으로 돈다고 생각하자.
-- 회전의 방향이 정해져있기 때문에 대각선 사방 탐색을 할 때 탐색 방향의 순서가 정해진다.
-- 회전 회수가 4인 상황에서 출발지와 현재 지점의 좌표가 동일하면 목적지를 잘 찾아온 것이다.
4. 투어 도중 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안된다.
-- 중복 방문을 하지 않기 위해서 일반적으로 visited를 사용할 수 있는데
-- 지도 전체에 대한 점검 보다는 먹은 디저트로 한정하는 것이 유리하다.
-- 따라서 이 문제에서 visited의 역할은 해당 디저트를 먹었는지에 대한 고민으로 대체한다.
5. 한 곳에서 하나만 먹고 끝내는 행위는 허용되지 않는다.
6. 어떤 지점에서 다른 지점으로 방문 시 가능한 모든 노드의 경우를 따져야 하는데
-- 이 문제에서는 회전해야 하기 때문에 매번 한칸 전진과 우회전만 고민하면 된다.
[입력 사항]
지도는 N*N으로 주어지고 N은 4 이상 20 이하의 정수이다. (4 ≤ N ≤ 20)
디저트의 종류는 1~100이하
[출력 사항]
가장 많이 먹을 때의 디저트 수를 출력하고 먹을 수 없는 경우 정답은 -1
* 분류: #dfs
동영상 설명
1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.
소스 보기
동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.
꼭 작성할 각오가 되어있습니다.
package se.code.모의;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;
public class SWEA_모의_2105_디저트카페 {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder output = new StringBuilder();
// 대각선 사방탐색
private static int[][] dirs = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
private static int TC;
private static int N; // 지도의 크기 N
private static int MAX; // 최대 디저트 개수
private static int[][] map;
public static void main(String[] args) throws IOException {
input = new BufferedReader(new StringReader(src));
TC = Integer.parseInt(input.readLine());
for (int t = 1; t < TC + 1; t++) {
N = Integer.parseInt(input.readLine());
map = new int[N][N];
StringTokenizer tokens = null;
for (int r = 0; r < N; r++) {
tokens = new StringTokenizer(input.readLine());
for (int c = 0; c < N; c++) {
map[r][c] = Integer.parseInt(tokens.nextToken());
}
}
// 입력 완료
MAX = Integer.MIN_VALUE;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
// 각각의 지점에서 디저트를 먹고 출발해본다.
Node node = new Node(r, c, 0);
boolean[] eatenDeserts = new boolean[101];
findPath(node, node, eatenDeserts);
}
}
output.append("#").append(t).append(" ").append(MAX == Integer.MIN_VALUE ? -1 : MAX).append("\n");
} // for
System.out.println(output);
}// main
static void findPath(Node start, Node current, boolean[] eatenDeserts) {
// current가 목적지라면 별 고민없지롱~ - 최대값 비교 후 종료
if (current.d == 4) {
if (current.r == start.r && current.c == start.c) {
// System.out.println("출발지점에 왔어.!!!");
int cnt = 0;
for (int i = 0; i < eatenDeserts.length; i++) {
if (eatenDeserts[i]) {
cnt++;
}
}
MAX = Math.max(cnt, MAX);
}
return;
}
// 목적지가 아니라면 일단은 무조건 현재 방향으로 한칸은 전진한다.
int nr = current.r + dirs[current.d][0];
int nc = current.c + dirs[current.d][1];
// System.out.println(current.r + " : " + current.c + "> " + nr + " : " + nc);
if (isIn(nr, nc)) {
// 전진한 곳에 있는 디저트가 처음 본거라면..
if (eatenDeserts[map[nr][nc]] == false) {
// 먹어서 방문 처리 방문 처리
eatenDeserts[map[nr][nc]] = true;
// 자식 노드 찾기 - 직진이거나 방향 회전 하거나.
// 현재 방향으로 직진하는 경우
Node nodeDirect = new Node(nr, nc, current.d);
findPath(start, nodeDirect, eatenDeserts);
// 방향 회전 고민 : 아직 방향이 3이하면 방향 회전 해보자.
Node nodeTurn = new Node(nr, nc, current.d + 1);
findPath(start, nodeTurn, eatenDeserts);
// 흐름이 실패했다면 방문 안한척 하기 - 그냥 int를 이용한 삭제는 index를 의미하므로 주의할것!!!
eatenDeserts[map[nr][nc]] = false;
}
}
}
private static boolean isIn(int r, int c) {
return 0 <= r && r < N && 0 <= c && c < N;
}
static class Node {
int r, c, d;// row, col, dir
int t; // 디저트 타입
public Node(int r, int c, int d) {
super();
this.r = r;
this.c = c;
this.d = d;
t = map[r][c];
}
@Override
public String toString() {
return "[r=" + r + ", c=" + c + ", t=" + t + ", d=" + d + "]";
}
}
static String src = "10\n" +
"4\n" +
"9 8 9 8\n" +
"4 6 9 4\n" +
"8 7 7 8\n" +
"4 5 3 5\n" +
"5\n" +
"8 2 9 6 6\n" +
"1 9 3 3 4\n" +
"8 2 3 3 6\n" +
"4 3 4 4 9\n" +
"7 4 6 3 5\n" +
"6\n" +
"1 8 9 6 3 9\n" +
"5 3 1 9 8 2\n" +
"6 9 3 4 1 2\n" +
"7 1 1 5 1 9\n" +
"1 9 6 8 7 3\n" +
"7 6 4 5 5 5\n" +
"7\n" +
"7 4 1 5 1 7 9\n" +
"9 4 6 1 4 6 8\n" +
"9 6 4 8 4 7 4\n" +
"3 2 6 2 4 2 8\n" +
"4 9 4 6 2 4 7\n" +
"1 7 6 8 9 5 8\n" +
"1 9 4 7 2 9 7\n" +
"8\n" +
"18 18 7 16 15 3 5 6\n" +
"3 6 8 3 15 13 15 2\n" +
"4 1 11 17 3 4 3 17\n" +
"16 2 18 10 2 3 11 12\n" +
"11 17 16 2 9 16 5 4\n" +
"17 7 6 16 16 11 15 8\n" +
"2 1 7 18 12 11 6 2\n" +
"13 12 12 15 9 11 12 18\n" +
"9\n" +
"12 3 10 8 11 12 5 3 11\n" +
"8 6 4 9 8 2 4 7 6\n" +
"6 10 12 8 3 8 11 3 3\n" +
"6 10 5 5 5 11 8 10 2\n" +
"5 13 3 7 5 6 5 12 6\n" +
"6 1 5 4 4 13 8 7 2\n" +
"12 7 13 3 5 1 11 7 3\n" +
"13 12 7 5 6 12 12 9 6\n" +
"1 12 13 13 11 3 4 10 9\n" +
"10\n" +
"18 8 21 24 8 4 20 15 14 23\n" +
"17 22 3 14 3 19 19 7 6 13\n" +
"2 26 10 10 10 7 18 14 15 17\n" +
"13 25 7 20 18 21 8 2 4 24\n" +
"4 3 1 5 15 3 15 12 22 23\n" +
"19 22 9 17 6 9 22 26 2 5\n" +
"12 13 19 13 6 2 12 19 24 8\n" +
"21 21 24 15 4 1 20 13 14 5\n" +
"6 10 17 13 7 4 22 16 9 7\n" +
"17 8 12 11 20 13 5 24 11 3\n" +
"11\n" +
"19 1 20 18 8 11 21 11 4 19 14\n" +
"14 17 6 10 19 3 5 9 18 20 7\n" +
"4 8 9 3 3 1 3 17 3 19 21\n" +
"20 19 13 21 20 17 5 21 15 3 10\n" +
"18 1 7 16 19 21 15 8 7 17 5\n" +
"21 1 3 11 14 4 15 10 14 15 17\n" +
"5 15 5 12 16 5 15 14 8 11 5\n" +
"14 18 2 19 19 8 5 7 11 11 1\n" +
"20 9 13 8 16 4 21 20 12 16 1\n" +
"9 11 7 18 5 19 5 18 13 18 20\n" +
"5 16 1 12 6 15 8 15 3 18 7\n" +
"14\n" +
"11 31 22 3 36 20 10 23 6 5 22 22 19 29\n" +
"9 7 13 9 31 15 7 1 13 33 11 24 7 36\n" +
"21 22 6 19 23 4 6 21 14 36 9 4 30 21\n" +
"17 2 30 13 26 36 2 13 32 27 36 5 28 16\n" +
"8 20 12 16 31 10 32 15 19 24 34 20 1 16\n" +
"17 18 22 3 10 2 30 26 27 29 10 16 24 12\n" +
"25 32 31 20 10 29 19 11 32 23 28 20 33 24\n" +
"9 13 19 4 6 27 24 5 16 2 8 34 2 7\n" +
"21 5 5 26 2 35 7 36 21 22 23 33 2 6\n" +
"16 21 15 21 12 11 13 28 3 3 14 23 16 4\n" +
"1 31 35 33 23 29 12 18 24 25 19 33 17 13\n" +
"29 6 30 19 33 14 35 14 6 23 27 16 12 24\n" +
"26 31 30 10 16 21 7 4 16 25 31 19 21 8\n" +
"12 5 2 4 4 27 29 2 18 20 19 26 32 31\n" +
"20\n" +
"11 34 7 49 59 88 79 12 63 38 13 27 9 70 97 92 86 95 84 18\n" +
"11 84 39 44 86 86 59 52 61 97 81 94 92 78 32 7 5 62 41 75\n" +
"15 61 71 27 3 4 79 51 95 99 73 27 75 31 4 7 15 51 50 16\n" +
"6 81 32 61 75 24 36 26 57 55 52 15 35 44 30 25 2 54 12 25\n" +
"42 4 66 1 23 44 1 7 63 27 82 70 40 45 4 3 12 35 11 85\n" +
"97 55 69 49 34 79 37 69 89 66 85 22 23 88 24 79 1 48 85 72\n" +
"4 67 23 3 27 18 37 61 7 68 88 80 35 21 42 88 38 10 81 84\n" +
"78 86 21 50 46 13 50 9 54 3 1 94 85 75 80 45 31 100 29 70\n" +
"9 59 7 48 81 82 43 68 90 37 26 41 84 31 58 42 4 96 86 20\n" +
"22 4 49 94 74 42 6 38 84 90 29 95 84 36 18 4 10 34 71 26\n" +
"46 43 7 88 18 21 96 57 3 72 52 83 50 53 56 51 19 50 57 6\n" +
"15 30 88 26 49 10 6 12 98 81 47 88 82 2 68 85 62 12 92 88\n" +
"100 31 5 15 76 84 39 10 52 61 28 12 50 22 35 85 1 83 2 76\n" +
"17 27 83 45 18 4 95 37 23 96 58 49 36 47 13 10 41 38 37 6\n" +
"22 92 59 68 51 15 65 88 18 69 40 49 7 11 78 14 95 94 45 27\n" +
"13 36 33 22 29 49 11 10 50 91 15 71 87 83 63 26 76 89 28 9\n" +
"98 9 96 58 72 79 28 9 63 67 85 16 40 66 46 47 17 85 16 99\n" +
"42 87 28 97 60 89 92 90 51 60 96 22 51 95 55 44 16 9 51 69\n" +
"27 45 53 43 45 52 12 90 86 91 47 39 84 9 21 77 69 56 5 69\n" +
"99 47 66 91 71 2 9 26 43 54 52 30 4 94 97 92 2 67 12 85";
}
Contents
소중한 공감 감사합니다