본문 바로가기
공부-코딩테스트/코테풀이 - 자바, 파이썬

1210. [S/W 문제해결 기본] 2일차 - Ladder1 (SWEA, 자바, 코딩테스트)

by 령과 2022. 8. 2.

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

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com


풀이

  1. 전부 다 확인할 필요없이 도착점을 기준으로 거슬러 올라가는 사다리타기 룰을 적용하면 바로 찾을 수 있다.
  2. 생각할 고려사항은 크게 3가지이다.
    1) 계속 올라가는 경우
    2) 갈림길을 만나서 옆으로 틀어야 하는 경우
    3)막다른 상황이라 다시 올라가는 경우
  3. 아래 LCR 변수를 통해서 이전의 방향을 기억해둔다. -1이면 왼쪽으로 가던 상황 1이면 오른쪽으로, 0은 위로
  4. 재귀를 사용해서 반복하다보면 x값이 0이되는 상황이 시작점을 만난 상황이므로 해당 x값을 return하면 된다.

나의 코드

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

class Solution {
	static int[][] table = new int[100][100];

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int T = 10;
		for (int test_case = 1; test_case <= T; test_case++) {
			String trash = bf.readLine();
			for (int i = 0; i < table.length; i++) {
				StringTokenizer st = new StringTokenizer(bf.readLine());
				for (int j = 0; j < table[i].length; j++) {
					table[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			solution(test_case);
		}

	}
	public static void solution(int tc) {
		for (int i = 0; i < table[99].length; i++) {
			if (table[99][i] == 2) {
				int answer = check(98, i, 0);
				System.out.println("#" + tc + " " + answer);
				break;
			}
		}
	}

	public static int check(int x, int y, int LCR) {
		if (x == 0) {
			return y;
		} else {
			boolean pass_L = check_road(x, y - 1);
			boolean pass_R = check_road(x, y + 1);
			if (!pass_L && !pass_R) { // 모두 막힌 부분 -> 아래로 이동가능할 것
				return check(x - 1, y, 0);
			} else if (pass_L && pass_R) { // 모두 이동 가능한 경우 -> 옆으로 이동중인 경우
				return check(x, y + LCR, LCR);

			} else if (pass_L || pass_R) {// 한쪽만 열린 경우 => 경로를 틀어야 할때와 아래로 내려가야 할 경우
				if (LCR == 0) {// 아래로 내려가고 있다가 경로트는 경우
					int tmp_LCR = pass_L ? -1 : 1;
					return check(x, y + tmp_LCR, tmp_LCR);
				} else {// 경로 틀다가 아래로 내려가야 하는 경우
					return check(x - 1, y, 0);
				}

			} else {// 이거뜨면 문제있는거
				return -1;
			}
		}
	}
	public static boolean check_road(int x, int y) {
		if (y < 0 || y >= 100 || table[x][y] == 0) {
			return false;
		}
		return true;
	}
}

댓글