2105.(모의 SW 역량테스트) 디저트 카페
2105. (모의 SW 역량테스트) 디저트 카페
문제의 저작권은 SWEA에 있습니다
대각선을 잘 그리면 되는 문제.
삼성공채 SW 역량테스트를 준비하기 전날에 풀까말까 하다가 안풀고 다른 구현문제를 풀었었는데,
이 문제를 풀고 시험을 봤다면 시간이 부족하지는 않았을텐데 라는 후회를 하게 만든 문제.
여하튼, 나중에 이 문제를 풀때 역시 2019 하반기 공채 삼성 SW역량테스트 오전 1번문제를 풀듯이 풀어봤는데,
생각보다 빡빡하고 시간도 오래걸렸다. (모든 경우의 수를 조건문으로 고려하는 구현방법으로 풀어서)
단순히, 방향과 프루닝(가지치기), 조건을 건 백트래킹을 사용하면 굉장히 파워풀하고 직관적이며 간단한 코드를 짤 수 있다.
dfs 백트래킹 짱짱
혹시 비슷한 문제를 풀어보고 싶으시다면 아래 링크를 들어가서 풀어보세요!
삼성 SW역량테스트 오전 1번문제 입니다.
백준 - 게리맨더링2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
import java.util.Scanner;
public class Solution {
static int[][] map;
static int[] dr = {1,1,-1,-1};
static int[] dc = {1,-1,-1,1};
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int tc=1; tc<=T; tc++) {
N = sc.nextInt();
map = new int[N][N];
ans = -1;
for(int i=0; i<N; i++) for(int j=0; j<N; j++) map[i][j] = sc.nextInt();
for(int i=0; i<N-2; i++) {
for(int j=1; j<N-1; j++) {
recur(i,j, i ,j , new boolean[101], 0, 1);
}
}
System.out.println("#"+tc+" "+ans);
}//end test cases
}//end main
static int ans;
static void recur(int tr, int tc, int nr, int nc, boolean[] desert, int dir, int sum) {
desert[map[nr][nc]]=true;
// 방향 초과(0~3)
if(dir>3) return;
// 각 방향에 따른 좌표 변화
nr += dr[dir];
nc += dc[dir];
//돌아서 원래 점으로 돌아옴
if(nr==tr && nc==tc) {
ans = Math.max(ans, sum);
return;
}
// 가장 위에 찍힌 점보다 더 위에 올라갈 수 없음.(작을 수 없음)
if(nr<tr) return;
if(nr<0 || nc<0 || nr> N-1|| nc>N-1) return;
//이미 방문했던 디저트 가게라면 return
if(desert[map[nr][nc]]) return;
desert[map[nr][nc]]=true;
recur(tr,tc,nr,nc,desert, dir, sum+1);
recur(tr,tc,nr,nc,desert, dir+1, sum+1);
desert[map[nr][nc]]=false;
}//end recur
}
|
cs |
'Algorithm > SWEA' 카테고리의 다른 글
SWEA] 2112. [모의 SW 역량테스트] 보호 필름 (1) | 2019.11.03 |
---|---|
SWEA] 1949. [모의 SW 역량테스트] 등산로 조성 (0) | 2019.11.02 |
SWEA] 4796. 의석이의 우뚝 선 산 (0) | 2019.10.01 |
SWEA] 3131. 100만 이하의 모든 소수 (0) | 2019.08.17 |