문제
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
풀이
위에서 시작해서 도착점을 찾는것보다는 도착지부터 시작해서 위로 올라가는것이 더 효율적이다.
도착지에서부터 시작하면 왼쪽, 오른쪽, 위쪽 3 방향으로만 이동 가능하다.
오른쪽이나 왼쪽이 위로 올라가는 것보다 우선순위이기 때문에 오른쪽, 왼쪽으로 이동가능하면 이동할 수 있도록 한다.
기존에 위치한 좌표는 더이상 방문 불가하기 때문에 옮기기 전에 방문했다는 표시를 하고 옮겨야 한다.
코드
import java.io.*;
import java.util.*;
public class Solution {
static int board[][];
static int answer;
static int dx [] = {0, 0, -1};
static int dy [] = {1, -1, 0};
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for(int test_case = 1; test_case <= 10; test_case++)
{
board = new int [100][100];
answer = 0;
int t = Integer.parseInt(br.readLine());
int depX = 0;
int depY = 0;
for(int i=0;i<100;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<100;j++) {
board[i][j] = Integer.parseInt(st.nextToken());
if(board[i][j] == 2){
depX = i;
depY = j;
}
}
}
ladder(depX, depY);
System.out.println("#"+test_case+" "+answer);
}
}
static void ladder(int x, int y) {
while(true) {
if(x == 0) {
answer = y;
break;
}
board[x][y] = 3;
for(int i=0;i<3;i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 100 || ny >= 100 || nx < 0 || ny < 0) continue;
if(board[nx][ny] == 1) {
x = nx;
y = ny;
break;
}
}
}
}
}