알고리즘/SWEA
[JAVA][SW Expert Academy] 1211. Ladder2
minddi
2022. 8. 13. 04:13
[SW Expert Academy] 1211. Ladder2
※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제 내용
| 점심 시간에 산책을 다니는 사원들은 최근 날씨가 더워져, 사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기로 한다. 김 대리는 사다리타기에 참여하지 않는 대신 사다리를 그리기로 하였다. 사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 최단거리로 바닥에 도착하게 되는지 궁금해졌다. 이를 구해보자. 아래 <그림 1>의 예를 살펴보면, 출발점 x=0 및 x=9인 세로 방향의 두 막대 사이에 임의의 개수의 막대들이 랜덤 간격으로 추가되고(이 예에서는 2개가 추가됨) 이 막대들 사이에 가로 방향의 선들이 또한 랜덤하게 연결된다. X=0인 출발점에서 출발하는 사례에 대해서 화살표로 표시한 바와 같이, 아래 방향으로 진행하면서 좌우 방향으로 이동 가능한 통로가 나타나면 방향 전환을 하게 된다. 방향 전환 이후엔 다시 아래 방향으로만 이동하게 되며, 바닥에 도착하면 멈추게 된다. 최단거리로 바닥에 도착하려면 X=4인 출발점에서 출발해야 하므로 답은 4가 된다. 해당 경로는 별도로 표시하였다.  <그림 1> 사다리 게임에 대한 설명(미니맵)
아래 <그림 2>와 같은 100 x 100 크기의 2차원 배열로 주어진 사다리에 대해서, 모든 출발점을 검사하여 바닥까지 가장 짧은 이동 거리를 갖는 시작점 x(복수 개인 경우 가장 큰 x좌표)를 반환하는 코드를 작성하라.(‘0’으로 채워진 평면상에 사다리는 연속된 ‘1’로 표현된다.)  <그림 2> 테스트 케이스에 의해 생성되는 실제 사다리의 모습
[제약사항 한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다. [입력] 각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다. 총 10개의 테스트 케이스가 주어진다. [출력] #부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도착하게 되는 출발점의 x좌표를 출력한다. |
해결 순서
1. 1210. Ladder1 문제의 응용 케이스 (https://minz-sw.tistory.com/10)
2. 출발지점부터 도착지점으로 이동하는 시작 x 좌표로 도착지점까지의 거리 구하기
3. 출발지점에서 도착지점으로 가는 y 좌표의 이동 거리는 모든 케이스가 동일하므로 count에서 제외해도 무관
5. x좌표에 변화가 생기면 count
6. (특이사항) 1210. Ladder1에서는 발견하지 못한 문제가 확인됐는데, 배열을 파라미터로 넘기는 경우 원래의 배열값도 변경되는 문제 발생. (해당 배열의 주소 내 값을 변경해서 그런건지 잘 모르겠다. 해당 내용은 알게되는대로 업데이트 예정) 그래서 인자로 받은 배열을 동일하게 복제하여 사용하는 방법으로 코딩
문제 풀이
|
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
|
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T = 10;
for(int test_case = 1; test_case <= T; test_case++)
{
int TC = sc.nextInt();
int[][] arrLadder = new int[100][100];
int minCnt = 0, maxKey = 0;
HashMap<Integer, Integer> m_cnt = new HashMap<>();
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
arrLadder[j][i] = sc.nextInt();
}
}
for (int i = 0; i < 100; i++) {
if (arrLadder[i][0] == 1) {
m_cnt.put(i, direction(arrLadder, i, 0));
}
}
int[] arrKey = new int[m_cnt.size()];
int seqKey = 0;
for (int key : m_cnt.keySet()) {
arrKey[seqKey] = key;
seqKey++;
}
Arrays.sort(arrKey);
minCnt = m_cnt.get(arrKey[0]);
for (int i = 1; i < arrKey.length; i++) {
if (m_cnt.get(arrKey[i]) <= minCnt) {
minCnt = m_cnt.get(arrKey[i]);
maxKey = arrKey[i];
}
}
System.out.println("#" + TC + " " + maxKey);
}
}
public static int direction(int[][] arrLadder, int ePointX, int ePointY) {
int cnt = 0;
int[][] arr = new int[100][100];
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
arr[j][i] = arrLadder[j][i];
}
}
while (ePointY < 99) {
if (ePointX > 0 & ePointX < 99) {
if (arr[ePointX - 1][ePointY] == 1) {
arr[ePointX][ePointY] = -1;
ePointX--;
cnt++;
} else if (arr[ePointX + 1][ePointY] == 1) {
arr[ePointX][ePointY] = -1;
ePointX++;
cnt++;
} else {
ePointY++;
}
} else if (ePointX == 0){
if (arr[ePointX + 1][ePointY] == 1) {
arr[ePointX][ePointY] = -1;
ePointX++;
cnt++;
} else {
ePointY++;
}
} else {
if (arr[ePointX - 1][ePointY] == 1) {
arr[ePointX][ePointY] = -1;
ePointX--;
cnt++;
} else {
ePointY++;
}
}
}
return cnt - 1;
}
}
|
cs |