[SWEA]1210번 Ladder1(JAVA)

0. 문제 링크

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

SW Expert Academy

 

1. 문제 설명

1) 100x100 크기의 2차원 배열로 주어진 사다리

2) x=0인 출발점에서 출발하여 아래 방향으로 진행하면서 좌우 방향으로 이동 가능한 통로가 나타나면 방향 전환

2) 도착점에 도착했을 때 출발점 x 구하기

 

2. 입출력

// input
1
1 0 0 1 ...

// output
#1 67
...

 

3. 코드

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

public class swea1210 {
	static int[] dr = {0, 0, -1}; // 탐색 범위
	static int[] dc = {-1, 1, 0};
	static int[][] map;
	static int ans = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		int T = 10; // 테스트 케이스의 개수
		for(int t = 1; t <= T; t++) {
			Integer.parseInt(br.readLine()); // 테스트 케이스 순서
			int r = 0, c = 0; // 도착점의 r, c
			map = new int[100][100]; // 2차원 배열의 사다리
			
			// 입력
			for(int i = 0; i < 100; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j = 0; j < 100; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(map[i][j] == 2) { // 도착 지점에서 시작
						r = i;
						c = j;
					}
				}
			}
			
			move(r, c); // 탐색
			
			// 출력
			System.out.println("#" + t + " " + ans);
		}
	}

	private static void move(int i, int j) {
		while(true) {
			if(i == 0) { // 첫 줄로 오면 종료
				ans = j;
				break;
			}
			
			for(int d = 0; d < 3; d++) {
				int nr = i + dr[d]; // 삼방탐색
				int nc = j + dc[d];
				
				if(nr >= 0 && nr < 100 && nc >= 0 && nc < 100 && map[nr][nc] == 1) {
					map[nr][nc] = 3; // 방문 처리
					i = nr;
					j = nc;
				}
			}
		}
	}
}

 

실행 결과

 

4. 회고

1) 배열의 크기가 100x100 이기 때문에 빠르게 받아오기 위해서 BufferedReader 사용

2) 이동 가능한 통로가 나타나면 왼쪽, 오른쪽으로 이동하고, 아니면 아래로만 이동 -> 삼방탐색

3) 방문 배열을 새로 사용하는 것보다 방문한 곳을 다른 값으로 변경하여 방문 체크

 

5. Github

https://github.com/iihye/Algorithm/blob/main/SWEA/swea1210.java