SWE Ladder1

100 x 100 배열에서 arr[i][j]=2인 곳을 목적지로 하는 arr[0][i]의 i를 찾는 문제이다.

 

같은 방향으로 나아가다가 다음 위치에 1이 아니거나 다음 위치가 인덱스를 벗어나면 방향을 바꾼다. 아래로만 향하고 오른쪽이나 왼쪽이 있으면 방향을 바꾸며 나아간다. 재귀를 통해 반복하다가 arr[i][j]=2이면 탈출한다.

 

package day0803;

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

public class Ladder {
	static int [][]arr;
	static int ans;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		for (int t = 1; t <= 10; t++) {
			int test = Integer.parseInt(bf.readLine());
			arr = new int[100][100];
			for (int i = 0; i < 100; i++) {
				String s = bf.readLine();
				StringTokenizer st = new StringTokenizer(s);
				for (int j = 0; j < 100; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());

				}
			}

			for (int i = 0; i < 100; i++) {
				if (arr[0][i] == 1)
					findWay(0, i, i,1,arr);
			}
			System.out.println("#"+t+" "+ans);
		}
	}

	static void findWay(int i, int j, int start,int direc,int [][]arr) {
	//y축 좌표, x축 좌표, 처음 출발지의 위치, 방향,배열
		
		
		if(direc==2) {//오른쪽
			if(j+1<100 && arr[i][j+1]==1 ) { //계속 오른쪽 방향으로 나아갈 수 있을때
				findWay(i,j+1,start,2,arr);
			}
			else {
				findWay(i+1,j,start,1,arr); //아래방향으로 내려가기
			}
			
		}
		else if(direc==3) {//왼쪽
			if(j-1>=0 && arr[i][j-1]==1 ) //계속 왼쪽 방향으로 나아갈 수 있을 때
				findWay(i,j-1,start,3,arr);
			else findWay(i+1,j,start,1,arr); //아래방향으로 내려가기
		}
		
		else { //아래 방향
			if(j+1<100 && arr[i][j+1]==1 ) { //오른쪽으로 나아갈 수 있을 때
				findWay(i,j+1,start,2,arr);
			}
			else if(j-1>=0 && arr[i][j-1]==1 ) {//왼쪽으로 나아갈 수 있을 때
				findWay(i,j-1,start,3,arr);
			}
			else {
				if(i<99) //아래방향으로 나아가기
				findWay(i+1,j,start,1,arr);
			}
		}
		
	
		if(i==99) {//최종 99줄에 도착했을 때
			if(arr[i][j]==2) { //만약 도착지라면
		
				ans=start; //답을 출발지로 바꿈
			}
			return ;
		}
	}
	
	
	

}