[SWEA / Java] 1210번: Ladder1 (D4)

문제 풀이 날짜: 2023.08.01
포스트 작성일: 2023.08.01

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

SWEA 1210번: Ladder1 (D4)

 

키워드

배열 탐색

 

풀이 접근법

• 입력 배열 중, 2가 적힌 곳의 좌표로부터 시작점을 찾아가는 탐색 문제.
• 배열의 맨 아래부터 위로 올라가거나 왼쪽, 오른쪽으로 이동하면 되기 때문에 delta 배열에는 왼쪽, 오른쪽, 위쪽 방향의 변량만 정의한다.
•  
• private static int[] dr = { 0, 0, -1 }; private static int[] dc = { -1, 1, 0 };
• 왼쪽, 오른쪽 사다리를 만나면 무조건 이동해야 하기 때문에 왼쪽, 오른쪽 방향은 위쪽 방향보다 우선권을 가진다. 따라서 delta 배열에서 위쪽 이동의 변량을 가장 마지막 원소로 정의한다.
• 위쪽으로 이동하다가 왼쪽, 오른쪽 좌표에 1이 있다면 (사다리가 있다면) 해당 방향으로 이동한다. 이동하고 다음 이동을 위해 현재 좌표를 갱신해준다.
  • 이 때, 이미 방문했던 곳을 다시 방문할 수 없도록 배열 값을 1 이외의 값으로 수정한다. 만약 재방문을 막지 않았다면 사다리를 건넜다가 다시 원래 지점으로 되돌아갈 수도 있다.

 

코드

import java.util.*;
import java.io.*;

public class Solution {
	private static final int N = 10;

	private static int[] dr = { 0, 0, -1 };
	private static int[] dc = { -1, 1, 0 };

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = 1;

		int[][] matrix = new int[N][N];

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {
			int tc = Integer.parseInt(br.readLine());

			int startR = 0;
			int startC = 0;
			StringTokenizer st;
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					matrix[i][j] = Integer.parseInt(st.nextToken());

					if (matrix[i][j] == 2) {
						startC = j;
						startR = i;
					}
				}
			}

			int result = move(matrix, startR, startC);

			sb.append("#").append(test_case).append(" ").append(result).append("\n");
		}

		System.out.println(sb);
	}

	private static int move(int[][] matrix, int r, int c) {

		int nr = 0;
		int nc = 0;
		while (nr >= 0 && nc >= 0) {
			for (int i = 0; i < dr.length; i++) {
				nr = r + dr[i];
				nc = c + dc[i];

				if (!isValid(nr, nc)) {
					continue;
				}

				if(matrix[nr][nc] == 1) {
					matrix[nr][nc] = 3;
					r = nr;
					c = nc;
				}
			}
		}
		
		return nc;
	}

	private static boolean isValid(int nr, int nc) {
		return (nr > -1 && nc > -1 && nr < N && nc < N);
	}
}

 

---

 

 

git 링크

(git 링크 첨부)