1210. Ladder1

오늘은 브루트포스 알고리즘, 완전탐색을 배웠는데...

매우 힘겨웠다 ^^

 

1. 문제

 

점심 시간에 산책을 다니는 사원들은 최근 날씨가 더워져, 사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기로 한다.

김 대리는 사다리타기에 참여하지 않는 대신 사다리를 그리기로 하였다.

사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 X표시에 도착하게 되는지 궁금해졌다. 이를 구해보자.

아래 <그림 1>의 예를 살펴보면, 출발점 x=0 및 x=9인 세로 방향의 두 막대 사이에 임의의 개수의 막대들이 랜덤 간격으로 추가되고(이 예에서는 2개가 추가됨) 이 막대들 사이에 가로 방향의 선들이 또한 랜덤하게 연결된다.

X=0인 출발점에서 출발하는 사례에 대해서 화살표로 표시한 바와 같이, 아래 방향으로 진행하면서 좌우 방향으로 이동 가능한 통로가 나타나면 방향 전환을 하게 된다.

방향 전환 이후엔 다시 아래 방향으로만 이동하게 되며, 바닥에 도착하면 멈추게 된다.

문제의 X표시에 도착하려면 X=4인 출발점에서 출발해야 하므로 답은 4가 된다. 해당 경로는 별도로 표시하였다.

 

 

아래 <그림 2>와 같은 100 x 100 크기의 2차원 배열로 주어진 사다리에 대해서, 지정된 도착점에 대응되는 출발점 X를 반환하는 코드를 작성하라 (‘0’으로 채워진 평면상에 사다리는 연속된 ‘1’로 표현된다. 도착 지점은 '2'로 표현된다).

 

 

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

SW Expert Academy

 

 

2. My 코드

 

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		
		for(int test=1;test<11;test++) {
			// 1. test case input
			int test_case = sc.nextInt();
			
			//2. 100x100
			int[][] radder = new int[100][100];
			int[][] radder_copy = new int[100][100];
			int[] start = new int[100];
			int start_count=0;
			int idx=0; //idx-1 만큼 start가 있는 것 
			for(int r=0;r<100;r++) {
				for(int c=0;c<100;c++) {
					radder[r][c]=sc.nextInt();
					//3. 사다리 출발 위치를 찾는다.
					if(r==0 && radder[r][c]==1) {
						start[idx++]=c; //col 위치 넣음 
					}
				}
			}
			
			radder_copy=radder.clone();
			
			//3. 사다리 돌자
			int flag=-1; //도착지를 갔는지? 도착지가면 col값 들어감 
			int result=0;
			outer: for(int rad_col=0;rad_col<idx;rad_col++) {
				
				int r=0;
				int c=start[rad_col];
				result=c;
				//System.out.println("new!! "+c);
				//System.out.println("out while "+c);
				//바닥에 닿는 순간 끝!
				
				while(r<99 && flag==-1) {
					
					//오 체크
					if(right(radder_copy, r, c)) {
						//System.out.println("right "+r +" "+c);
						radder_copy[r][c]=9;//visited
						c++;
						if(radder_copy[r][c]==2) {
							flag=c;
							break outer;
						}
					}
					
					//왼 체크
					else if(left(radder_copy, r, c)) {
						//System.out.println("left "+r+" "+c);
						radder_copy[r][c]=9;//visited
						c--;
						if(radder_copy[r][c]==2) {
							flag=c;
							break outer;
						}
					}
					
					
					//바텀 체크
					else if(bottom(radder_copy, r, c)) {
						//System.out.println("bottom "+r+" "+c);
						radder_copy[r][c]=9;//visited
						r++;
						if(radder_copy[r][c]==2) {
							flag=c;
							break outer;
						}
						
					}
	
				}//while end
				//다른 출발지에서 가기 위해 사다리 원상복구
				//visited = 9 -> 1
				for(int a=0;a<100;a++) {
					for(int b=0;b<100;b++) {
						if(radder_copy[a][b]==9) {
							radder_copy[a][b]=1; 
						}
					}
				}
			}//outer end

			//결과출력 
			//flag=-1이 아니라는 것은 정답에 닿았다는 뜻 col값이 들어가 있음
			//if(flag!=-1) System.out.println("#"+test+" "+flag);
			System.out.println("#"+test+" "+result);
		}//test case end
	}
    
    //좌 우 아래 판단 함수
	public static boolean left(int[][] radder, int r, int c) {
		boolean result = false;
		if(r>=0 && r<100 && c>0 && c<100) {
			if(radder[r][c-1]==1 || radder[r][c-1]==2) {
				result=true;
			}
		}
		return result;
	}
	
	public static boolean right(int[][] radder, int r, int c) {
		
		boolean result = false;
		if(r>=0 && r<100 && c>=0 && c<99) {
			
			if(radder[r][c+1]==1 ||radder[r][c+1]==2) {
				result=true;
				
			}
			
		}
		return result;
	}
	
	public static boolean bottom(int[][] radder, int r, int c) {
		boolean result = false;
		if(r>=0 && r<99 && c>=0 && c<100) {
			if(radder[r+1][c]==1 || radder[r+1][c]==2) {
				result=true;
			}
		}
		return result;
	}
}

재귀함수로도 풀 수 있다는데, 나중에 배우면 써먹어 봐야겠다.