[SWEA] 1210. [S/W 문제해결 기본] 2일차 - Ladder1 (Java)

문제 링크 / level: D4

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh&categoryId=AV14ABYKADACFAYh&categoryType=CODE

SW Expert Academy

 

 

내가 생각한 풀이

난이도도 D4인데다가, 그림만 보면 약간 무시무시한 느낌도 들지만 꼼꼼히 읽고 차근차근 생각해보면 그리 어렵지 않게 해결할 수 있는 문제였다.😎✌

 

이번에는 메모장에 적어보았다.

간단하게라도 내가 생각한 로직을 글로 옮겨야 정리가 좀 될 것 같아서 메모장을 켜고 간단히 적어보았다.

 

생각을 정리해보자!!

문제의 핵심은 '2'로 입력되는 도착점에서부터 출발점을 찾기 위해 거슬러 올라가는 것이다.

즉, 원래 사다리타기는 출발점에서부터 도착점까지 길을 따라 이동하는 방식이지만 이 문제를 풀기 위해서는 거꾸로 올라가면 된다.

 

그리하여 내가 생각한 기본 로직:

1. 기본적으로는 위 방향으로 계속 올라간다.

2. 한 칸 올라갈 때마다 좌, 우를 살피면서 길이 있나 확인한다.

3. 길이 있다면 그 방향으로 길이 없거나 벽이 나올 때까지(=배열의 범위를 벗어나기 전까지) 이동하고, 길이 없다면 위로 한 칸 올라간다.

 

참 쉽죠?😆

 

---

 

일단 input값을 다 입력받은 후에는 가장 먼저 도착지점부터 어딘지 찾아준다.

당연하게도 도착지점은 index=99인 행에 있을 거다. 그러니까 그 행만 for문을 돌려서 탐색해주면 된다.

// 도착점 찾기
for (int i = 0; i < 100; i++) {
	if (map[99][i] == 2) {
		Ans = searchStartPoint(99, i);
		break;
	}
}

이 안에다가 코드를 마저 짤 수도 있었겠지만 로직이 살짝 길어질 것 같아서 따로 메소드로 빼줬다.

(+ 내용 추가) 원래 break;를 넣을 생각을 못했었는데 다시 보다보니까 break;를 넣는 것이 좀 더 효율적일 것 같아서 코드를 수정했다.

 

---

 

그리고 이제 코드의 핵심 로직을 구현해주면 끝!!!

// 핵심 코드
static int[] dx = { -1, 1 };
private static int searchStartPoint(int y, int x) {
	// 출발점을 찾을 때까지 반복 (계속 위로 올라갈 예정)
	while (true) {
		if (y == 0) {break;} // 만약 출발점을 찾았다면 끝내기.
		road = false;
		// 올라가기 전에 좌, 우를 먼저 살핀다
		for (int d = 0; d < 2; d++) {
			int nx = x + dx[d];
			if (nx < 0 || nx >= 100) {continue;}
			if (map[y][nx] == 1) { // 만약 좌 or 우에 길이 있다면
				road = true;
				x = nx; // 옆으로 한 칸 이동하고,
				// 그 때의 방향으로 계속 이동 (0이나 벽이 나올 때까지)
				while (true) {
					nx = x + dx[d]; // 여기서 방향(d값)은 고정되어 있음
					if (nx < 0 || nx >= 100 || map[y][nx] == 0) {break;}
					else {x = nx;}
				}
			}
			if (road) {break;}
		}
		y--;
	}
	return x;
}

- 좌, 우로만 이동하기 때문에 dx 배열에는 -1와 1 값만 넣어준다. y 값은 굳이 필요 없음.

- 출발점을 찾을 때까지 몇 번 이동할지 알 수 없기 때문에 while문을 이용한다. --> break되는 시점은? 출발점을 찾았을 때! 즉, index=0인 행에 도달했을 때 while문을 벗어나도록 설계했다.

- 좌, 우로 이어지는 길을 찾았는지 확인하기 위해 road라는 boolean type의 변수를 활용했다. 로직이 수행되는 시작 부분에서 false로 초기화해주는 것은 필수!

- 만약 출발점에 도달하지 않았다면 아직 위로 더 올라가야 하니 로직을 수행한다. 

 

<로직>

👩 일단 좌, 우를 살피며 길이 있다면 road 값을 true로 업데이트 하고, 그 방향으로 한 칸 이동한다.

👩 그리고 길이 있다는 것은 곧 그 옆으로 이어진 길이 더 있다는 것! 하지만 그 길이 어디까지 이어지는지는 알 수 없으므로 while문을 이용해서 배열의 범위를 벗어나거나 (nx < 0 || nx >= 100) 길이 아닌 곳이 나올 때 (map[y][nx] == 0) 까지 해당 방향으로 쭉 이동하도록 했다. 길을 발견했을 때의 d값을 계속 가지고 있으므로 원하는 방향으로 계속 이동시킬 수 있다.

👩 위 로직을 마친 후에는 if (road) {break;} 라는 코드를 거치도록 했다. 만약 길이 있었다면 이 코드를 만남으로써 좌, 우를 살피는 과정을 마칠 것이다. 잘 생각해보면 사다리타기에서 좌나 우 둘 중 하나의 길만 있는거니까. 그 전에 길이 있었다면 다른 방향은 더 살펴볼 필요 없겠지?

 

위 과정을 모두 마쳤다면 두 가지 상황이 가능하다.

1. 길을 찾았고, 그 방향으로 길이 없을 때까지 이동을 완료한 상태.

2. 길을 찾지 못한 상태. 즉, 위로 올라가야 한다.

 

나는 처음에는 2번 케이스에서만 위로 한 칸 이동시켰는데 테스트케이스를 몇 개 돌려보니 오류를 발견할 수 있었다.

생각해보니까 좌, 우로 난 길을 찾아서 쭉 이동하고 더 이상 길이 없어서 멈췄을 때에도 위로 올라가도록 해야했던 것이었고 것이었던 것이었다!!!😲 (고마워요 테스트케이스^_^)

 

그렇게 해서 오류를 수정하고 제출하나 했더니만 또 다른 오류가 발견됐다..

바로 if (nx < 0 || nx >= 100 || map[y][nx] == 0) {break;} 이 코드에서 였는데, 지금은 순서를 바꿔뒀지만 처음에는 아무 생각 없이 map[y][nx] == 0 이 코드를 맨 앞에 둬서 배열 범위를 벗어나는 exception이 발생했었다. 이런 디테일을 항상 조심하도록 하자😂

 

아무튼 결론은 통과!!

나름 재미있는 문제였던 것 같다.🤗💚

 

 

💌 전체 코드 보기:

https://github.com/psS2mj/Problem_Solving_SWEA_by_JAVA/blob/master/D4/Solution_1210_Ladder1.java

psS2mj/Problem_Solving_SWEA_by_JAVA