[SWEA] JAVA - 1210 Ladder1

(설명 오늘내로 업로드 예정입니다!!)

 

재귀함수로 문제를 풀고싶어 y=0이고 좌표값이 1인 x 좌표들 중에서 출발하여 y가 마지막 행 까지 도달할때 해당 x 좌표값을 반환하는 재귀 함수를 구현하려고 시도하였습니다. 하지만 이렇게 시작을 문제에서 주어진대로 접근하는 경우 보다 문제를 거꾸로 뒤집어서 도착점~출발점 을 찾아가는 방식으로 풀어야 한다는것을 배운 문제였습니다.

 

우선 도착점에서 시작하여 좌,우 방향으로 방향 전환이 가능할경우 방향 전환을 해주었습니다. 만약 좌우 방향 모두 이동할수없을 경우 전진 이동을 해야합니다. (저는 좌우 방향의 이동 우선순위가 더 높은줄 모르고, 이동 분기점에서 제일 첫번째 if문에 직진이 가능할 경우를 설정해서 코드를 수정했습니다 ㅠㅠ)

 

재귀함수로 구현한 go 함수에서 y=0일경우 x좌표를 리턴시켜줌으로써 재귀 함수의 base case를 설정했습니다.

 

추가

재귀적으로 풀지 않고 풀이한 방법은 solve 함수입니다. 좌우 방향으로 이동이 가능할경우 해당방향으로 전진이 가능할대까지 while문을 반복해줍니다. 만약 좌우방향 모두 이동이 안됄 경우 직진 이동이 가능할때까지 진행시켜줍니다.

 

package com.ssafy.off;

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

public class SWEA_1210_Ladder1 {
	final static int N = 100;
	static int answer;
	static int[][] map;
	static boolean [][] visited;
	
	private static int solve(int end, int[][] map) {
		int y = 99, x = end; // 도착점좌표
		while(y > 0) {
			//1. 오른쪽으로 이동 가능한지 -> 계속 오른쪽으로 이동
			if((x+1 < 100) && map[y][x+1] == 1) {
				do {
					x++;
				}while((x+1 < 100) && map[y][x+1] == 1);
			}
			//2. 왼쪽으로 이동 가능한지 -> 계속 왼쪽으로 이동
			else if((x-1 >= 0) && map[y][x-1] == 1) {
				do {
					x--;
				}while((x-1 >= 0) && map[y][x-1] == 1);
			}
			//3. 위로 이동
			y--;
		}
		return x;
	}
	
	private static void go(int nowY, int nowX) {
		visited[nowY][nowX] = true;
		if(nowY == 0) {
			answer = nowX;
			return;
		}
		else {
			
			if(nowX-1 < N && nowX-1 >= 0 && visited[nowY][nowX-1] == false && map[nowY][nowX-1] == 1) {//왼쪽 가능할때
				go(nowY, nowX-1);
			}
			else if(nowX+1 < N && nowX+1>=0 && visited[nowY][nowX+1] == false && map[nowY][nowX+1] == 1) {//오른쪽 가능할때
				go(nowY, nowX+1);
			}
			else if(nowY-1 < N && nowY-1 >=0 && visited[nowY-1][nowX] == false && map[nowY-1][nowX] == 1) {//위로 가능할때
				go(nowY-1, nowX);
			}

		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		//100x100 크기 사다리에서 도착지점(2)로 갈수있는 출발점 x를 반환 (x는 0부터)
		//아래 왼쪽 오른쪽 탐색
		//recursion
		//go()
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		for (int t = 1; t <= 10; t++) {
			map = new int[N][N];
			visited = new boolean[N][N];
			answer = 0;
			int startY = 0, startX = 0;
			//입력
			int tc = Integer.parseInt(in.readLine());
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(map[i][j] == 2) {
						startY = i;
						startX = j;
					}
				}
			}//입력 끝
			
			//solve
			//go(startY, startX);
			answer = solve(startX, map);
			System.out.println("#" + t + " " + answer);
		}

	}

}