[1일 1알고리즘] SW Expert Academy 1210. Ladder1 풀이

문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh 

SW Expert Academy

이전에 풀이에 실패하고 지나갔던 문제를 다시 풀어보았다.

100 by 100 배열은 사다리로 이어져있으며, 목적지로 갈 수 있는 시작점을 출력하는 문제이다.

 

내가 처음에 설계한 알고리즘 흐름

입력값 받기

함수 (2의 x위치, 2의 y 위치)
nx = x ; ny = y; 
무한반복{
맵을 안 벗어나면서 왼쪽이 1이면 
무한반복{
다음값 = 왼쪽값
만약 왼쪽이 0일경우 빠져나옴 
}

오른쪽로직도 왼쪽과 동일

다음값 = y값유지한채 위로 한칸올라간다
만약 x값이 0이 되는경우 y값 리턴
}

위의 로직대로 코드를 구현했더니 10개의 테스트 케이스 중 1개만 맞음.

 

문제 조건에 따르면, 한 방향으로 더 이상 갈 수 없으면 위(아래)로 올라(내려) 가야 하는데 디버깅 결과 왼쪽을 탐색하고 break문을 빠져나와서 오른쪽 방향으로 다시 들어가는 문제점이 발생함.

 

해결방안 : flag를 사용하여 왼쪽 사다리가 있는 경우 true 오른쪽 사다리 검사 시 flag가 false 경우에만 확인하도록 함.

 

위 방법으로 수정해도 10개 중 3개만 맞았음. 맞지 않는 케이스를 디버깅한 결과 사다리의 위치가 양 끝일 경우 조건을 배제했다는 것을 알아냈다. 

 

해결방안 : 양끝에 도달할 경우 while문을 빠져나오도록 if문 조건 추가.

 

소감 : 문제 설계 시 나의 코드가 예외상황까지 커버되는지 충분한 검토 후 코드를 작성하는 것이 좋겠다.

 

통과 소스 코드(가급적 정답 코드는 보지 말고 스스로 풀어보시고, 참고로만 봐주세요.) 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution_1210_Ladder1 {
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("input (10).txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[][] map = new char[100][100];
		int sx = 0, sy = 0;
		for (int tc = 1; tc <= 10; tc++) {
			br.readLine();
			for (int i = 0; i < 100; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 100; j++) {
					map[i][j] = st.nextToken().charAt(0);
					if (map[i][j] == '2') {
						sx = i;
						sy = j;
					}
				}
			} // 입력완료
				int ans = find(map, sx, sy);
			
			System.out.println("#" + tc + " " + ans);
		}
	}

	private static int find(char[][] map, int sx, int sy) {
		int nx = sx;
		int ny = sy;
		boolean flag;
		while (true) {
			flag = false;
			if (nx >= 0 && nx < 100 && ny >= 1 && ny < 101 && map[nx][ny - 1] == '1') {
				flag = true;
				while (true) {
					ny -= 1;
					if (ny == 0 || ny >= 1 && ny < 101 && map[nx][ny - 1] == '0')
						break;
				}
			}

			if (!flag && nx >= 0 && nx < 100 && ny >= -1 && ny < 99 && map[nx][ny + 1] == '1') {
				while (true) {
					ny += 1;
					if (ny == 99 || ny >= -1 && ny < 99 && map[nx][ny + 1] == '0')
						break;
				}
			}
			nx -= 1;
			if (nx == 0)
				break;
		}

		return ny;
	}

}

 

input 데이터가 공백으로 구분되며 숫자이기 때문에 Scanner의 nextInt를 사용해도 됩니다.

(단, 입력 처리시간은 BufferedReader가 더 빠름.)

BufferedReader를 사용할 경우 String값으로 처리되기 때문에 StringTokenizer를 이용하여 2차원 char배열에 값을 저장했습니다.

char 타입의 경우 비교 연산자 사용 시 작은따옴표('') 유의.

델타 배열을 사용해도 되지만 로직이 복잡하지 않기 때문에 굳이 사용하지 않았습니다. 

배열의 인덱스에 접근할 때는 배열 범위를 벗어나지 않는지 조건문을 통해 우선적으로 체크하는 것이 좋음.