https://www.acmicpc.net/problem/17265
17265번: 나의 인생에는 수학과 함께
세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로
www.acmicpc.net
보통의 dfs문제는 방문한 위치를 다시 방문하지 않기 위해 boolean 2차원 배열을 사용해서 방문기록을 남겼다.
하지만 이번 문제는 오른쪽과 아래로만 이동하기 때문에 따로 방문기록을 남기지 않아도 된다!! (재밌는 문제였다)
[풀이 방법]
1. 우선 이때까지 지나온 길의 값들을 모두 저장할 ArrayList구조를 갖는 클래스 변수 exp 선언
2. exp에 현재 위치(집)의 값을 추가하고 출발
3. 아래, 오른쪽 뱡향으로 이동 시도
-> 만약 이동하려는 위치가 범위를 벗어나면 다음방향으로 이동 시도
-> 범위를 벗어나지 않는다면 exp의 맨 마지막에 다음위치의 값을 추가
4. 학교에 도착했다면 이때까지 걸어온 길의 수식을 계산한 뒤, 최솟값 최대값과 비교하여 갱신
(수식을 계산하는 메서드는 dfs에서 빼서 따로 구현)
[구현코드_Java]
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
static int N;
static int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
static String[][] road;
static int[] dx = {1, 0};
static int[] dy = {0, 1};
static ArrayList<String> exp = new ArrayList<>();
public static void main(String[] args) {
//입력받은 값 각 변수에 저장
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
road = new String[N][N];
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
road[i][j] = sc.next();
}
}
exp.add(road[0][0]);
dfs(0, 0);
System.out.print(max);
System.out.print(" ");
System.out.println(min);
}
public static void dfs(int x, int y) {
if((x == N - 1) && (y == N - 1)) { //학교에 도착하면 탐색 종료
int result = getResult();
min = Math.min(result, min);
max = Math.max(result, max);
return;
}
for(int i = 0; i < 2; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
//다음위치가 범위를 벗어날 경우 다음 방향으로 이동
if(nx < 0 || nx >= N || ny < 0 || ny >=N) continue;
exp.add(road[nx][ny]);
dfs(nx, ny);
exp.remove(exp.size() - 1);
}
}
public static int getResult() { //이때까지 지나온 길의 수식을 계산
int result = cal(exp.get(0), exp.get(1), exp.get(2));
for(int i = 3; i < exp.size(); i += 2) {
result = cal(Integer.toString(result), exp.get(i), exp.get(i + 1));
}
return result;
}
public static int cal(String n1, String op, String n2) { //연신기호에 따라 계산
if("+".equals(op)) return Integer.parseInt(n1) + Integer.parseInt(n2);
else if("-".equals(op)) return Integer.parseInt(n1) - Integer.parseInt(n2);
else return Integer.parseInt(n1) * Integer.parseInt(n2);
}
}
'알고리즘' 카테고리의 다른 글
[백준] 11724번 연결 요소의 개수 (0) | 2022.07.12 |
---|---|
[백준] 2606번: 바이러스 (0) | 2022.07.04 |
[백준] 2178번 미로탐색 (0) | 2022.06.28 |
[백준] 14500번 테트로미노 (0) | 2022.06.22 |
[프로그래머스] [1차] 캐시 (0) | 2022.06.16 |