👩‍💻 SWEA_1210_Ladder1

YOU KNOW I MEAN·2021년 4월 24일

알고리즘

알고리즘 풀이과정 😎

목록 보기

3/17

💬 완전탐색으로 풀고 싶었는데 메모리초과가 발생했습니다. 이를 해결하기 위해 3구간으로 나눠 생각했습니다.

💡 풀이 방법

첫번째 시도

도착지점부터 출발해 출발지점을 찾고자했습니다.
아래 지점은 탐색을 안해도 되니 왼쪽, 오른쪽, 위쪽을 탐색하고 왼쪽, 오른쪽으로 가지 못할 경우 위쪽으로 가도록 하였습니다.
이미 지나온 길은 방문처리를 해주어 왔던 길을 다시 가지 않도록 하였습니다.

두번째 시도

방문 처리를 하니 메모리 초과가 발생했습니다.
확인하는 수를 줄이고자 flag 를 두어 왼쪽, 오른쪽, 위쪽인지 파악한 후 진행했습니다.
코너를 도는 부분일 경우 flag 에 해당하는 값만 가능 여부를 확인했습니다.
왼쪽, 오른쪽이 모두 안되면 flag 를 위쪽으로 값으로 설정하고 위로 한칸 이동했습니다.

세번째 시도

시간 초과가 일어났습니다.
알고보니 이동하는 값을 배열로 설정해주었는데 int ny = start_j - dy[k]; 빼주어서 문제가 발생했습니다.
int ny = start_j + dy[k]; 로 변경하니 문제가 해결되었습니다.

🔥 코드

package algorithm;

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

public class SWEA_1210_Ladder1 {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int dx[] = { 0, 0 };
		int dy[] = { -1, 1 };
		for (int t = 1; t <= 10; t++) {
			int T = Integer.parseInt(br.readLine());
			int answer = 0;
			int ladder[][] = new int[100][100];
			int start_j = 0;
			int start_i = 99;

			// 배열에 저장
			for (int i = 0; i < 100; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 100; j++) {
					int tmp = Integer.parseInt(st.nextToken());
					ladder[i][j] = tmp;
					if (tmp == 2) {
						start_j = j;
					}
				}
			}

			// 탐색
			int flag = 2;
			while (true) {
				if (start_i == 0) {
					answer = start_j;
					break;
				}

				// 위쪽
				if (flag == 2) {
					start_i -= 1;
					for (int k = 0; k < 2; k++) {
						int ny = start_j + dy[k];
						if (ny == -1 || ny == 100 || ladder[start_i][ny] == 0) {
							continue;
						}
						flag = k;
					}
				}

				// 왼쪽 혹은 오른쪽
				else {
					if (flag == 0) {
						int ny = start_j - 1;
						if (ny == -1 || ladder[start_i][ny] == 0) {
							flag = 2;
							continue;
						}
						start_j = ny;
					} else if (flag == 1) {
						int ny = start_j + 1;
						if (ny == 100 || ladder[start_i][ny] == 0) {
							flag = 2;
							continue;
						}
						start_j = ny;
					}
				}
			}
			System.out.println("#" + T + " " + answer);
		}
	}
}