(1210)(Ladder1) - s/w 문제 해결 기본 2일차

작성일

문제 이해

이 문제를 푸는 전략은 studyBook1(4)에서 배웠다.

1.모든 출발점을 다 조사할 필요 없이, 거꾸로 올라가는 방법을 취하자. 2.경계면 처리를 쉽게 해주기 위해서 102102로 공간을 잡았다. 즉 100100 배열 주위를 0이 둘러싸고 있는 모양이다.

  1. 가장 먼저 해야할 일은 도착점을 찾는 것이다.
  2. 그 이후 좌우를 살펴보고 없다면 위로 올라간다(y=100이므로 y–;) 좌우에 길이 있다면 그 길의 끝까지 이동한다. (길이 있다, 즉 좌우가 1이라면) 이 작업을 반복해서 수행하면 된다.
import java.util.Scanner;

public class Solution {
	
	// 배열에서 최소값을 찾는다.
	public static int search(int Map[][], int start) 
	{	
		int y  = 100 ; int x = start;
		
		while(y != 1)
		{
			if(Map[y][x-1] == 1) // 좌측 사다리가 있으면
			{
				while(Map[y][x-1] != 0) {//끝까지 이동한 뒤
					x--;
				}
				y--; //  위로 한칸 올라간다.
			}
			else if(Map[y][x+1] == 1) //우측 사다리가 있다면
			{
				while(Map[y][x+1] != 0)
				{
					x++;
				}
				y--;  // 위로 한칸 올라간다.
			}
			else{
				y--;
			}// 좌우측에 사다리가 없는 경우 위로 한칸 이동한다.
		}
		return x; 
	} 
		public static void main(String[] args) {
		
			Scanner stdIn = new Scanner(System.in);
			
			int i, j;
			
			int target = 0;
			
			for(int t = 0 ; t < 10; t++) {
				int num = stdIn.nextInt();
			
				//사다리 초기화
				int [][]Map = new int[102][102];
				
				for(i = 1; i<101; i++)
					for(j = 1; j< 101; j++)
						Map[i][j] = stdIn.nextInt();
				
				// 도착 지점 찾기
				for(i = 0 ; i< 102; i ++) {
					if(Map[100][i] == 2) {
						target = i;
						break;
					}
				}
				System.out.print("#"+num);
				System.out.println(search(Map,target)-1); //1을 왜 뺴줄까? ->위가 0이기 때문에 끝까지 올라가버린다.
			}
	}			
}

참고자료

소프트웨어 아카데미 S/W Problem Solving

배열 정렬 참고자료

https://defacto-standard.tistory.com/18

0%