SWExpertAcademy 1210번-Ladder(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh 

SW Expert Academy

 

[제약 사항]

한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다.

[입력]

입력 파일의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트 케이스가 주어진다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도착하게 되는 출발점의 x좌표를 출력한다.

 

import java.io.IOException;
import java.util.Scanner;

public class Ladder1 {
	private static int ladder(int r, int c, int dir, int[][] arr) { // 행, 열, arr
		// 종료 조건 row가 0일 때
		if (r == 0)
			return c;
		// 반복
		// 좌우 탐색 (온 방향으로 다시 되돌아가면 안되므로 direction 체크)
		// dir=0 -> 아래쪽에서 옴
		// dir=1 -> 왼쪽에서 옴
		// dir=2 -> 오른쪽에서 옴
		if ((c > 0 && arr[r][c - 1] == 1 && dir != 1) || (c < 99 && arr[r][c + 1] == 1 && dir != 2))
			return (c > 0 && arr[r][c - 1] == 1 && dir != 1) ? ladder(r, c - 1, 2, arr) : ladder(r, c + 1, 1, arr);
		return ladder(r - 1, c, 0, arr);
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int[][] arr = new int[100][100];
		int T = 10;
		int Testcase_num;
		for (int i = 0; i < T; i++) {
			// 입력부
			Testcase_num = sc.nextInt(); // 테스트 케이스 번호
			for (int j = 0; j < 100; j++) {
				for (int k = 0; k < 100; k++) {
					arr[j][k] = sc.nextInt();
				}
			}
			// 로직
			for (int j = 0; j < 100; j++) {
				if (arr[99][j] == 2) {
					sb.append("#" + Testcase_num + " " + ladder(99, j, 0, arr) + "\n");
					break;
				}
			}
		}
		// 출력부
		System.out.println(sb);
	}
}

 

사다리 타기 - 목적지부터 역순으로 재귀 탐색으로 접근하는 풀이입니다.

 

*ladder(int r, int c, int dir, int[][] arr)

-매개변수

int r= 탐색 기준 원소의 row

int c = 탐색 기준 원소의 column

int dir = 탐색 기준 원소가 온 방향

int[][] arr = 탐색할 사다리값 배열

 

-종료조건

탐색 기준 원소 row 가 0일 때 -> 해당 원소의 column 값을 리턴

 

-동작

// 좌우 탐색 (온 방향으로 다시 되돌아가면 안되므로 direction 체크)
// dir=0 -> 아래쪽에서 옴
// dir=1 -> 왼쪽에서 옴
// dir=2 -> 오른쪽에서 옴

//(배열의 index를 벗어나지 않게하는 조건) and (왼쪽(또는 오른쪽) 원소가 유효값인지 검사하는 조건) and (되돌아 가지 않게 하기 위한 조건) 코드의 색이 해당하는 조건과 동일하니 필요 시 참고하시면 되겠습니다. 
if ((c > 0 && arr[r][c - 1] == 1 && dir != 1) || (c < 99 && arr[r][c + 1] == 1 && dir != 2)) 

//왼쪽 원소가 유효값이면 ladder(r,c -1,2,arr) return

//오른쪽 원소가 유효값이면 ladder(r, c + 1, 1, arr) return
return (c > 0 && arr[r][c - 1] == 1 && dir != 1) ? ladder(r, c - 1, 2, arr) : ladder(r, c + 1, 1, arr);

//왼쪽과 오른쪽에 유효값이 없으면 윗 row가 반드시 유효값이므로 return ladder(r - 1, c, 0, arr)

return ladder(r - 1, c, 0, arr);

 

 

+ 출력 String을 만드는 코드 내부에서 ladder 작업을 수행하였습니다.

ladder은 arr의 가장 마지막 row, 첫 column 에서 시작하므로 99,0을 초기 매개변수로 넣어주었습니다.

 

for (int j = 0; j < 100; j++) {
if (arr[99][j] == 2) {
sb.append("#" + Testcase_num + " " + ladder(99, j, 0, arr) + "\n");
break;
}
}