728x90
https://www.acmicpc.net/problem/14500
// 코드
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
import java.util.*;
import java.io.*;
public class Main{
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int N, M;
static int[][] myArr;
static boolean [][]visited;
static int maxSum;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
myArr = new int[N][M];
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
myArr[i][j] = Integer.parseInt(st.nextToken());
}
}
visited = new boolean[N][M];
for(int r=0; r<N; r++) {
for(int c=0; c<M; c++) {
visited[r][c] = true;
// 'ㅜ'를 제외한 나머지 경우는 DFS로 탐색
dfs(r, c, 1, myArr[r][c]);
// 'ㅜ'는 별도로 처리
maxSum = Math.max(getLast(r, c), maxSum);
visited[r][c] = false;
}
}
System.out.println(maxSum);
}
static void dfs(int row, int col, int cnt, int sum) {
if(cnt >= 4) {
maxSum = Math.max(maxSum, sum);
return;
} else {
for(int d=0; d<dirs.length; d++) {
int nr = row + dirs[d][0];
int nc = col + dirs[d][1];
if((0<=nr&&nr<N) && (0<=nc&&nc<M) && !visited[nr][nc]) {
visited[nr][nc] = true;
dfs(nr, nc, cnt+1, sum + myArr[nr][nc]);
visited[nr][nc] = false;
}
}
}
}
static int getLast(int row, int col) {
int base = myArr[row][col];
int cnt = 0; // 4방탐색의 성공횟수
int min = Integer.MAX_VALUE;
// 중심점을 중심으로 사방 탐색
for(int d=0; d<dirs.length; d++) {
int nr = row + dirs[d][0];
int nc = col + dirs[d][1];
if((0<=nr&&nr<N) && (0<=nc&&nc<M)) {
cnt++;
base += myArr[nr][nc];
min = Math.min(min, myArr[nr][nc]);
}
}
// 4방 탐색이 4군데 다 성공했다면 최솟값을 빼주기
if(cnt == 4) {
return base - min;
} else if(cnt == 3) { // 3방향만 성공했다면 그대로 진행
return base;
} else { // 나머지 경우는 모양 만들기 실패
return -1;
}
}
}
|
cs |
// 복습
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
import java.util.*;
import java.io.*;
public class Main{
// 상, 하, 좌, 우
static final int[][] DELTAS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int N, M;
static int[][] arr;
static boolean[][] visited;
static int mySum = Integer.MIN_VALUE; // 답
// 1. dfs를 통해 4방향 탐색을 하면 'ㅜ'를 제외한 모든 모양을 만들 수 있다.
public static void dfs(int x, int row, int col, int sum) {
// 기저조건 : x == 4 이면 mySum과 sum의 값을 비교후 결과에 맞게 처리한 뒤 종료
if(x >= 4) {
mySum = Math.max(mySum, sum);
return;
}
// 4방향 탐색을 시작한다.
for(int i=0; i<4; ++i) {
int ny = row + DELTAS[i][0];
int nx = col + DELTAS[i][1];
if( ny<0 || ny>=N || nx<0 || nx>=M || visited[ny][nx]) continue;
visited[ny][nx] = true;
dfs( (x+1), ny, nx, (sum+arr[ny][nx]) );
visited[ny][nx] = false;
}
}
// 2.'ㅜ'를 4방향 탐색을 해준다.
// 중심을 기준으로 : 4방향 탐색을 모두했을 경우 그중 최솟값 하나를 빼주고 반환
// : 3방향 탐색을 하였을 경우 바로 반환
// : 그 밖에는 실패 했으므로 -1 반환
static int getExceptCase(int row, int col) {
int orginValue = arr[row][col];
int minValue = Integer.MAX_VALUE;
int cnt = 0;
// 중심을 기준으로 4방향 탐색
for(int i=0; i<4; ++i) {
int ny = row + DELTAS[i][0];
int nx = col + DELTAS[i][1];
if( ny<0 || ny>=N || nx<0 || nx>=M ) continue;
++cnt;
orginValue += arr[ny][nx];
minValue = Math.min(minValue, arr[ny][nx]);
}
if(cnt == 4) return (orginValue - minValue);
else if(cnt == 3) return orginValue;
else return -1;
}
// main
public static void main(String[] args) throws Exception{
// Please Enter Your Code Here
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
visited = new boolean[N][M];
arr = new int[N][];
for(int i=0; i<N; ++i) arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 모든위치에서 4방향 탐색을 통해 최대값을 구한다.
for(int row=0; row<N; ++row) {
for(int col=0; col<M; ++col) {
visited[row][col] = true;
// dfs를 통해 4방향 탐색을 하면 'ㅜ'를 제외한 모든 모양을 만들 수 있다.
dfs(1, row, col, arr[row][col]);
// 'ㅜ'를 4방향 탐색을 해준다.
mySum = Math.max(mySum, getExceptCase(row, col));
visited[row][col] = false;
}
}
bw.write(String.valueOf(mySum));
bw.flush();
bw.close();
br.close();
}
}
|
cs |
반응형
'CS > 알고리즘_삼성 SW 역량 테스트 기출 문제' 카테고리의 다른 글
삼성 SW 역량 테스트 기출 문제 : 시험 감독 (0) | 2021.10.14 |
---|---|
삼성 SW 역량 테스트 기출 문제 : 연산자 끼워넣기 (0) | 2021.10.13 |
삼성 SW 역량 테스트 기출 문제 : 뱀 (0) | 2021.10.13 |
삼성 SW 역량 테스트 기출 문제 : 2048 (Easy) (0) | 2021.10.12 |
삼성 SW 역량 테스트 기출 문제 : 구슬 탈출 2 (0) | 2021.10.11 |