[Baekjoon] 17265_나의 인생에는 수학과 함께

Gold V

문제(출처: https://www.acmicpc.net/problem/17265)

---

< 나의 인생에는 수학과 함께 >

 

문제 풀이

 

bfs를 활용하여 문제를 해결했다.

 

❓ 배열을 왜 이렇게 많이 썼는가?

최댓값과 최솟값을 저장하는 부분과 방문 여부를 표시할 때 각각 따로 배열을 둬서 확인하는 것이 편하다고 생각했기 때문이다.

 

❓ 최댓값과 최솟값의 배열을 특정 값으로 설정하여 방문 배열을 따로 만들지 않고 방문 표시 여부를 확인해도 되지 않는가?

처음에는 각 배열의 값을 -1로 초기화한 후 -1일 경우에 무조건 값을 업데이트하도록 구현하였다. 그 결과 틀렸습니다가 출력되었다. 그 이유는 연산한 값으로 -1이며 그 값이 최솟값인 경우에도 무조건 다른 값으로 업데이트해서 정확한 값을 얻지 못해 틀렸다고 생각한다. 그래서 방문 여부를 확인하는 배열을 따로 구현했다.

 

❓ 연산자인 경우에는 왜 방문 여부를 표시하지 않았는가?

방문여부는 피연산자일 경우에만 방문 여부로 표시했다. 연산자를 방문 표시를 할 경우 피연산자가 달라지면 이미 방문한 곳으로

연산하지 못하는 경우가 생긴다고 생각했기 때문이다.

 

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main { // 나의 인생에는 수학과 함께
	static char arr[][];
	static int dx[] = { 0, 1 };
	static int dy[] = { 1, 0 };

	static int max_arr[][], min_arr[][], n;
	static boolean max_visited[][], min_visited[][];

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

		n = Integer.parseInt(bf.readLine());

		arr = new char[n][n];
		max_arr = new int[n][n];
		min_arr = new int[n][n];
		max_visited=new boolean[n][n];
		min_visited=new boolean[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[i][j] = st.nextToken().charAt(0);
			}
		}

		bfs(0, 0, arr[0][0] + "");
		System.out.println(max_arr[n - 1][n - 1] + " " + min_arr[n - 1][n - 1]);
	}

	private static void bfs(int i, int j, String str) {
		Queue<String[]> queue = new LinkedList<>();
		queue.add(new String[] { Integer.toString(i), Integer.toString(j), str+" " });
		max_visited[i][j]=true;
		min_visited[i][j]=true;
		
		while (!queue.isEmpty()) {
			String temp[] = queue.poll();
			for (int k = 0; k < 2; k++) {
				int x = Integer.parseInt(temp[0]) + dx[k];
				int y = Integer.parseInt(temp[1]) + dy[k];
				if (x >= 0 && x < n && y >= 0 && y < n) {
					if (!Character.isDigit(arr[x][y])) { // 연산자
						queue.add(new String[] { Integer.toString(x), Integer.toString(y), temp[2] +arr[x][y] });
					} else { // 숫자

						String[] num_arr=temp[2].split(" ");

						int a = Integer.parseInt(num_arr[0]);
						char op = num_arr[1].charAt(0);
						int b = arr[x][y] - '0';
						
						int result = -1;
						if (op == '+') {
							result = a + b;
						} else if (op == '-') {
							result = a - b;
						} else if (op == '*') {
							result = a * b;
						}
						
						if (!max_visited[x][y] || max_arr[x][y] < result) {
							max_visited[x][y]=true;
							max_arr[x][y] = result;
						}
						if (!min_visited[x][y] || min_arr[x][y] > result) {
							min_visited[x][y]=true;
							min_arr[x][y] = result;
						}
						
						if(max_arr[x][y]==min_arr[x][y]) {
							queue.add(new String[] { Integer.toString(x), Integer.toString(y), max_arr[x][y] + " " });
						}else {
							queue.add(new String[] { Integer.toString(x), Integer.toString(y), max_arr[x][y] + " " });
							queue.add(new String[] { Integer.toString(x), Integer.toString(y), min_arr[x][y] + " " });
						}
					}
				}
			}
		}
	}
}

 

Main

- 지도의 크기(n) 입력

- arr: 지도 정보 저장

   min_arr, max_arr : 연산 결과의 최댓값 최솟값 저장

   min_visited, max_visited: 최댓값과 최솟값 연산의 방문 여부 저장

- bfs 함수 호출 후 연산 결과의 최댓값, 최솟값 출력

 

bfs

- queue : [x좌표, y좌표, 숫자+연산자]

- queue가 빌 때까지 반복 -> 오른쪽과 아래쪽으로 이동 -> 그 값이 연산자라면 queue에 저장 / 숫자라면 피연산자와 연산자 구분하여 연산한 값 저장 후 최댓값과 최솟값 업데이트 및 queue에 저장

 

---

생각🤔

 

---