[SWEA 1210] [S/W 문제해결 기본] 2일차 - Ladder1

문제

• SWEA 1210번
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

시간이 꽤 오래 걸렸던 문제였다.
먼저 어떻게 접근을 하면 좋을지 고민을 많이 했는데 도착점과 이어지는 출발점을 구하는것이므로, 반대로 생각하여 도착점에서부터 거꾸로 출발점까지 가는 경로를 생각하면 다른 출발점의 경로를 고려하지 않아도 된다.
위로 올라갈때 방향을 생각해보면, ↑를 디폴트로 하지만 ←나 →가 있는 경우 ←나 →로 이동한다. 따라서 우선순위가 ←와 →방향이기 때문에 나는 좌, 우측 확인 후 위쪽을 검사하도록 진행했다.
방향을 정할 때, 먼저 도착점에서 시작해서 좌측에 해당하는 좌표값을 nx, ny에 넣은 후 해당 좌표값이 적합한지 판단해야한다. 1. 범위안에 있는지 2. map[nx][ny]가 1인지 검사 후 모두 만족하면 현재 좌표값을 다음 좌표값인 nx, ny로 변경한다. 만약, 검사했을 때 모두 만족하지 못한다면 이번엔 우측 좌표값을 nx, ny에 넣은 후 위와 똑같이 반복해서 검사한다. 현재 좌표값을 다음 좌표값으로 변경해준 후, 방문했음을 표시하기 위해 map[nx][ny]=9를 넣어준다. 이는 꼭 필요한 작업이며 만약 넣지 않았을 경우 나중에 무한루프로 돌게 되므로 꼭! 주의하자.
이렇게 방향을 정하면서 사다리를 올라가다가 x가 0이 된다면 이는 출발점에 해당하게 된다. 출발점은 ‘열’에 해당하므로 해당 열을 답으로 출력해주면 원하는 출발점 위치를 구할 수 있다.

코드

import java.util.*;

public class Swea_1210 {
	static final int SIZE = 100;
	static final int T = 10;
	static int[][] map;
	static int[] di = { 0, 0, -1 }; // 좌, 우, 상
	static int[] dj = { -1, 1, 0 };
	static int r, c, Answer = 0; //좌표(행, 열)

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (int tc = 0; tc < T; tc++) {
			int idx = sc.nextInt(); //입력파일 속 시작번호
			map = new int[SIZE][SIZE];
			
			for(int i=0; i<SIZE; i++) {
				for(int j=0; j<SIZE; j++) {
					map[i][j] = sc.nextInt();
					if(map[i][j] == 2) {
						r = i; //출발점
						c = j;
						map[r][c] = 9; //방문 표시
					}
				}
			}
			
			//거꾸로 추적
			while(true) {
				//다음 방향 결정: 좌->우->상 순서
				for(int i=0; i<di.length; i++) {
					int nr = r + di[i];
					int nc = c + dj[i];
					
					//다음 좌표값 검사: 1. 범위안에 있고 2.1인 경우
					if(nr >= 0 && nc >= 0 && nr < SIZE && nc < SIZE && map[nr][nc] == 1 ) {
						map[nr][nc] = 9; //방문 표시
						r = nr;
						c = nc;
						break; //방향 결정되었으니 다음 좌표로 넘어감
					}
				}
				
				//만약 다음 방향이 0이면
				if(r == 0) {
					Answer = c; //출발점
					break; //추적 종료
				}
			}
			System.out.println("#"+idx+" "+Answer);
		}

	}
}