greenkang
그린 개발log
greenkang
전체 방문자
오늘
어제
  • 분류 전체보기 (28)
    • 알고리즘 (20)
    • MySQL (0)
    • 생각 (0)
    • 컴퓨터구조 (6)
    • Spring · SpringBoot (1)
    • Java (1)
    • 장애 대응 회고 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 프로그래머스 거리두기 java
  • 프로그래머스 거리두기 자바
  • 파이썬
  • 프로그래머스
  • 어셈블리어
  • 리트코드
  • TOPCODER알고리즘트레이닝
  • 백준7569
  • 백준7569 java
  • java
  • 백준 1065번 자바
  • 백준 24479번 자바
  • 컴퓨터구조
  • python
  • 백준 17265번
  • 알고리즘
  • 장애 대응 회고
  • 41. First Missing Positive
  • 백준
  • 자바

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
greenkang

그린 개발log

알고리즘

[백준] 17265번 나의 인생에는 수학과 함께

2022. 6. 30. 01:17

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
    '알고리즘' 카테고리의 다른 글
    • [백준] 11724번 연결 요소의 개수
    • [백준] 2606번: 바이러스
    • [백준] 2178번 미로탐색
    • [백준] 14500번 테트로미노
    greenkang
    greenkang

    티스토리툴바