본문 바로가기
문제풀기/구름톤 챌린지

구름톤 챌린지 2주 Day4 - 폭탄 구현하기 (2)

by project100 2023. 8. 25.

폭탄 구현하기 (2) (Java)

 

제출한 답 :

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer firstLine = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(firstLine.nextToken()); // 땅의 크기
        int K = Integer.parseInt(firstLine.nextToken()); // 폭탄을 떨어트릴 횟수

        char[][] map = new char[N][N]; // 땅의 상태 저장 배열
        int[][] bombs = new int[K][2]; // 폭탄 떨어트릴 좌표 배열

		// 땅의 상태 입력 받기
        for (int i = 0; i < N; i++) {
            String row = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = row.charAt(j * 2); // 공백을 건너뛰기 위해 j * 2 인덱스 사용
            }
        }

		// 폭탄 좌표 입력 받기
        for (int i = 0; i < K; i++) {
            StringTokenizer tokenizer = new StringTokenizer(br.readLine());
            bombs[i][0] = Integer.parseInt(tokenizer.nextToken());
            bombs[i][1] = Integer.parseInt(tokenizer.nextToken());
        }

		// 땅의 상태 저장 배열
        int[] dy = {0, -1, 0, 1, 0};
        int[] dx = {0, 0, 1, 0, -1};
        int[][] arr = new int[N][N];

        for (int[] bomb : bombs) {
            int y = bomb[0] - 1;
            int x = bomb[1] - 1;

            for (int i = 0; i < 5; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];

                if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
                if (map[ny][nx] == '#') continue;
                if (map[ny][nx] == '0') arr[ny][nx] += 1;
                if (map[ny][nx] == '@') arr[ny][nx] += 2;
            }
        }

		// 최대 폭탄 값 찾기
        int maxBombValue = 0;
        for (int[] row : arr) {
            for (int value : row) {
                maxBombValue = Math.max(maxBombValue, value);
            }
        }

        System.out.println(maxBombValue);
    }
}

이것도 한계인데.. 다음 문제는 더 못 풀듯?? 

 

문제 풀이

필요한 개념
  • 시뮬레이션
  • 행렬
분석

폭탄 구현하기(2) 문제는 기존의 폭탄 구현하기 문제에 몇 가지 조건이 추가된 문제입니다.

문제를 분석하면 아래와 같이 정리할 수 있을 꺼 같아요

  • 폭탄이 떨어지면, 떨어진 위치를 기준으로 십자가 영역의 폭탄 값이 조건에 따라서 증가
    • #는 폭탄 값의 영향을 받지 않음.
    • 0 이라면 폭탄 값이 1만큼 증가
    • @ 라면 폭탄 값이 2만큼 증가
  • 모든 폭탄이 떨어진 이후에, 폭탄 값이 가장 높은 값을 출력

위의 상태에서 K 개의 폭탄이 모두 떨어지는 것을 시뮬레이션 하면 문제는 해결할 수 있습니다.

문제 풀이

문제 풀이를 위해서 필요한 점들을 고민하면 우선 2차원 배열에서의 탐색이 필요합니다. 해당 방법이 기억이 나지 않는다면 2주차 2번 구름 찾기 깃발 해설지를 참고하고 오시면 좋습니다.

이후에는 시뮬레이션 문제이기 때문에 주어지는 폭탄 데이터를 입력 받아 문제의 요구 사항대로 구현하면 됩니다. 모든 폭탄이 떨어진 이후에, 행렬에서 가장 큰 값을 찾아야 합니다.

데이터의 입력

이전에 배운 것처럼 행렬에 데이터를 입력하려고 합니다. 단, 이번에는 모두 정수가 아니라 문자열이기 때문에 split() 으로 문자열을 배열로 변환한 후 matirx 에 추가하면 됩니다.

폭탄이 떨어지는 좌표는, 행렬의 인덱스가 0부터 시작한다는 점을 기억해 좌표 조정을 합니다. 주어지는 값에 각각 1씩 빼주면 됩니다.

import java.util.*;
public class Main {
    public static void main(String[] args) {
		int N = scanner.nextInt();
        int K = scanner.nextInt();
        scanner.nextLine(); // 줄바꿈 기호를 없애줍니다.
				// 문자열 행렬에 값을 추가해준다.
        String[][] matrix = new String[N][N];
        for (int i = 0; i < N; i++) {
            matrix[i] = scanner.nextLine().split(" ");
        }
				// 폭탄이 떨어지는 좌표를 입력받고, 좌표 조정을 해준다.
				for (int k = 0; k < K; k++) {
            int x = scanner.nextInt() - 1; // Adjusting index
            int y = scanner.nextInt() - 1; // Adjusting index
				}
    }
}
점수 행렬 만들기

자바는 2차원 배열을 선언하는 순간, 0으로 초기화가 되어 있습니다. 이런 점을 이용하여 점수만 기록할 행렬을 선언할 수 있습니다. 점수 행렬은 matrix[x][y] 의 값에 따라서 폭탄의 값을 기록하는 행렬입니다.

int[][] score = new int[N][N];
탐색을 구현하기

우선 폭탄을 한 번 떨어트리는 코드가 필요합니다.

하나의 폭탄이 떨어지면 상하좌우에 폭탄의 영향을 끼치고, 영향을 받은 위치의 값에 따라서 영향을 끼치는 정도가 달라집니다. 그리고 폭탄의 영향은 떨어진 위치도 받기 때문에, dx/dy 기법에서는 원래 위치와 더불어, 상하좌우를 탐색할 수 있도록 코드를 작성하면 됩니다.

// 원래 위치와 상하좌우
int[] dx = {0, 0, 0, 1, -1};
int[] dy = {0, 1, -1, 0, 0};

구현과 탐색을 할 때 중요한 점은 탐색을 해도 되는 부분인지 확인해야 합니다. 이 문제에서 행렬의 범위를 넘어가는 경우와, 행렬의 값이 # 이라면 탐색 하지 않아도 문제가 없거든요.

그래서 현재의 (x, y) 에서 탐색을 진행했을 때, 범위를 나가거나, matrix[nx][ny] 의 값이 # 이라면 탐색을 하지 않도록 했습니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
				// matrix, score 행렬 선언 부분
				..code
        int[][] score = new int[N][N];

        for (int k = 0; k < K; k++) {
			// 떨어지는 폭탄의 위치를 x, y에 할당하고, 인덱스를 조정합니다.
            int x = scanner.nextInt() - 1; // Adjusting index
            int y = scanner.nextInt() - 1; // Adjusting index
						
			// dx/dy가 5곳을 탐색하기 때문에 반복문의 길이도 5입니다.
            for (int i = 0; i < 5; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
				// 행렬의 범위를 나가거나, 탐색할 행렬의 값이 #이라면 탐색하지 않습니다.
                if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                    if (!matrix[nx][ny].equals("#")) {
				// 폭탄 값의 영향을 받는 경우의 구현
                    }
                }
            }
        }
		}
}
폭탄을 구현하기

자 이제 마지막으로 구현할 부분은 다음과 같습니다.

  1. 땅의 상태가 0 이라면 폭탄 값은 1 증가한다.
  2. 땅의 상태가 @ 이라면 폭탄 값은 2 증가한다.

이 문구를 봤을 때, 땅의 상태는 matrix 에서 조회하고, 폭탄 값은 score 에서 조회하면 됩니다. 이를 글로 정리하면 아래처럼 됩니다.

matirx[nx][ny] 의 값이 @ 일 때,

score[nx][ny] 의 값을 2 추가합니다.

matirx[nx][ny] 의 값이 0일 때,

score[nx][ny] 의 값을 1 추가합니다.

글로 정리하니, 생각보다 간단합니다. 요즘 자주 보이는 이러한 구현 문제는 조건이 깔끔하게 정리되어 있어야 합니다. 잘 정리 되어 있을 수록 코드를 작성할 때 어려움도 없고 시간도 단축됩니다.

또 코드를 작성하다가 틀리거나 오류가 발생한 부분도 확실하게 체크할 수 있죠.

위의 글을 코드로 나타내면 아래와 같습니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
				// matrix, score 행렬 선언 부분
				..code
        int[][] score = new int[N][N];

        for (int k = 0; k < K; k++) {
	       // 떨어지는 폭탄의 위치를 x, y에 할당하고, 인덱스를 조정합니다.
            int x = scanner.nextInt() - 1; // Adjusting index
            int y = scanner.nextInt() - 1; // Adjusting index
						
						// dx/dy가 5곳을 탐색하기 때문에 반복문의 길이도 5입니다.
            for (int i = 0; i < 5; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
			// 행렬의 범위를 나가거나, 탐색할 행렬의 값이 #이라면 탐색하지 않습니다.
                if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                    if (!matrix[nx][ny].equals("#")) {
			//matrix[nx][ny]의 값이 @ 일때, score[nx][ny] 값을 +2 을 한다.
						if (matrix[nx][ny].equals("@")) {
                            score[nx][ny] += 2;
                        } 
			// matrix[nx][ny]값이 @가 아니라면, score[nx][ny] 값을 +1 을 한다.
												else {
                            score[nx][ny] += 1;
                        }
                    }
                }
            }
        }
		}
}
행렬에서 최대값 찾기

이 부분은 꼭 알아야 하는 부분은 아니지만, 알려드리고 싶어서 추가로 작성했습니다. score 행렬에는 지금 모든 폭탄 값들이 저장되어 있습니다. 이 행렬에서 최대 폭탄 값을 찾는 방법은 간단합니다. 이렇게 모든 배열을 순회하면서 Math.max() 를 활용해서 최대 값을 찾으면 됩니다.

int result = 0;
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        result = Math.max(result, score[i][j]);
    }
}

System.out.println(result);

정답

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        scanner.nextLine(); // 줄바꿈 기호를 없애줍니다.

        String[][] matrix = new String[N][N];
        for (int i = 0; i < N; i++) {
            matrix[i] = scanner.nextLine().split(" ");
        }

        int[] dx = {0, 0, 0, 1, -1};
        int[] dy = {0, 1, -1, 0, 0};
        int[][] score = new int[N][N];

        for (int k = 0; k < K; k++) {
            int x = scanner.nextInt() - 1; // Adjusting index
            int y = scanner.nextInt() - 1; // Adjusting index

            for (int i = 0; i < 5; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                    if (!matrix[nx][ny].equals("#")) {
                        if (matrix[nx][ny].equals("@")) {
                            score[nx][ny] += 2;
                        } else {
                            score[nx][ny] += 1;
                        }
                    }
                }
            }
        }

        int result = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                result = Math.max(result, score[i][j]);
            }
        }

        System.out.println(result);
        scanner.close();
    }
}
저작자표시 비영리 변경금지

'문제풀기 > 구름톤 챌린지' 카테고리의 다른 글

구름톤 챌린지 3주 Day1 - 통증 (2)  (0) 2023.09.02
구름톤 챌린지 2주 Day5 - GameJam  (0) 2023.09.02
구름톤 챌린지 2주 Day3 - 통증  (0) 2023.08.24
구름톤 챌린지 2주 Day2 - 구름 찾기 깃발  (0) 2023.08.23
구름톤 챌린지 2주 Day1 - 이진수 정렬  (0) 2023.08.22

관련글

티스토리툴바