[백준] 4396 지뢰 찾기

U_U·2024년 2월 20일

문제

https://www.acmicpc.net/problem/4396

접근방법

2차원 배열을 사용하여, 방향과 입력값을 저장하여 구현하는 방식

8가지의 방향 (상하좌우 + 대각선)

	static int [][] dist  = {
    {0,0,-1,1,-1,-1,1,1},
    {-1,1,0,0,-1,1,-1,1}
    };

방향을 쉽게 알아보기 위해 개행을 많이 해뒀다.

순서대로 하, 상, 좌, 우,왼쪽 아래, 왼쪽 위, 오른쪽 아래, 오른쪽 위 이다.

이 8가지 방향으로 mine을 찾는 함수는 아래와 같이 작성했다.
bfs에서 다음 이동 칸을 찾는것과 동일한 방식으로 구현했다.

	public static int findMine(int x,int y) {
		int mineCnt =0;
		for(int i=0;i<8;i++) {
			int nextX = x+dist[0][i];
			int nextY = y+dist[1][i];
			if(nextX<0 || nextX > N-1 || nextY<0 || nextY>N-1) continue;
			if(board[nextX][nextY]=='.') continue;
			mineCnt++;
		}
		return mineCnt;
	}

지뢰 처리 방식

열린칸이고 지뢰가 없는 칸이라면, 근처에 지뢰가 몇개인지 확인

열린칸이고 지뢰가 있다면, Mineflag = true

이외의 값은 모두 .으로 입력

마지막으로 Mineflag가 true라면 모든 지뢰는 *로 변경

처음에는 2단계에서 지뢰칸이기 때문에 *을 입력했지만, 어차피 나중에 넣을 건데 굳이? 라는 생각에 지웠다.

정답 코드 (String 배열)

import java.io.*;
import java.util.*;

public class Main {
	
	static class Node{
		int x,y;
		Node(int x, int y){
			this.x = x;
			this.y = y;

		}
	}
	static String[][] board;
	static String[][] user;
	static String[][] answer;
	static int N;
	static int [][] dist  = {{0,0,-1,1,-1,-1,1,1},{-1,1,0,0,-1,1,-1,1}};
	static ArrayList<Node> mine = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		board = new String[N][N];
		user = new String[N][N];
		answer = new String[N][N];
		
		
		for(int i=0;i<N;i++) {
			String [] strs = br.readLine().split("");
			for(int j=0;j<N;j++) {
				board[i][j] = strs[j];
				if(strs[j].equals("*")) mine.add(new Node(i,j));
			}
		}
		for(int i=0;i<N;i++) {
			String [] strs = br.readLine().split("");
			for(int j=0;j<N;j++) {
				user[i][j] = strs[j];
			}
		}
		
		solution();
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				System.out.print(answer[i][j]);
			}
			System.out.println();
		}
		
	}
	public static void solution() {
		boolean flag = false;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(user[i][j].equals("x") && board[i][j].equals(".")) {
					int mine = findMine(i,j);
					answer[i][j] = String.valueOf(mine);
				}
				else if(user[i][j].equals("x") && board[i][j].equals("*")) {
					answer[i][j]="*";
					flag = true;
				}
				else {
					answer[i][j] = ".";
				}
				if(flag) {
					for(Node node : mine) {
						answer[node.x][node.y] = "*";
					}
				}

			}
		}
	}
	public static int findMine(int x,int y) {
		int mineCnt =0;
		for(int i=0;i<8;i++) {
			int nextX = x+dist[0][i];
			int nextY = y+dist[1][i];
			if(nextX<0 || nextX > N-1 || nextY<0 || nextY>N-1) continue;
			if(board[nextX][nextY].equals(".")) continue;
			mineCnt++;
		}
		return mineCnt;
	}

}

처음에는 String 자료형과 함수가 익숙해서 String으로 문제를 풀었는데, char로도 충분히 가능할 것 같았다. char가 문자열 한개만 다루기 때문에 String보다 더 효율이 좋지 않을까? 생각해서 char로 코드를 수정해보았는데 ...

GPT 말로는 성능적인 차이는 없다고 한다 ... ^^
작은 규모의 데이터와 적은 루프 횟수, 단순 연산이기 때문이라고 한다..

요즘 성능과 튜닝에 관심이 많아져서, 정확한 String과 char의 차이를 찾아보고 추후에 이 내용을 추가해둘 예정.

아래는 String에서 char로 변경한 내용들과 정답코드이다.

String -> char

board[i][j] = strs[j]; //board가 String일때

board[i][j] = strs[j].charAt(0); //board가 char일때

strs는 BufferedReader로 받은 String이기 때문에 한글자여도 char로 변환을 해줘야 한다 !
어차피 한 글자인 String이기 때문에 charAt()을 이용해서 첫글자를 board에 저장했다.

if(user[i][j].equals("x") && board[i][j].equals(".")) //board가 String일때

if(user[i][j]=='x' && board[i][j]=='.') //board가 char일때

String에서는 같은 값을 비교하기 위해서 equals()함수를 사용하지만, char는 ==로 연산이 가능하다.
하지만 조심해야 할 점은 "x"가 아닌 'x'를 써야한다는 점 !!
처음에 char로 구현하다가 이 비교가 계속 에러가 나서 ... 그냥 전부다 String으로 변경해서 풀었다.

int -> String vs int -> char

answer[i][j] = String.valueOf(mine); //board가 String일때

answer[i][j] = Character.forDigit(mine,10); //board가 char일때

String에서는 valueOf()함수를 쓰면 쉽게 바뀌지만,
char은 Character.forDigit(바꿀 값, 진수)를 입력해야한다.

정답코드 (char 배열)

import java.util.*;

public class Main {
	
	static class Node{
		int x,y;
		Node(int x, int y){
			this.x = x;
			this.y = y;

		}
	}
	static char[][] board;
	static char[][] user;
	static char[][] answer;
	static int N;
	static int [][] dist  = {{0,0,-1,1,-1,-1,1,1},{-1,1,0,0,-1,1,-1,1}};
	static ArrayList<Node> mine = new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		board = new char[N][N];
		user = new char[N][N];
		answer = new char[N][N];
		
		
		for(int i=0;i<N;i++) {
			String [] strs = br.readLine().split("");
			for(int j=0;j<N;j++) {
				board[i][j] = strs[j].charAt(0);
				if(strs[j].equals("*")) mine.add(new Node(i,j));
			}
		}
		for(int i=0;i<N;i++) {
			String [] strs = br.readLine().split("");
			for(int j=0;j<N;j++) {
				user[i][j] = strs[j].charAt(0);
			}
		}
		
		solution();
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				System.out.print(answer[i][j]);
			}
			System.out.println();
		}
		
	}
	public static void solution() {
		boolean flag = false;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(user[i][j]=='x' && board[i][j]=='.') {
					int mine = findMine(i,j);
					answer[i][j] = Character.forDigit(mine,10);
				}
				else if(user[i][j]=='x' && board[i][j]=='*') {
					flag = true;
				}
				else {
					answer[i][j] = '.';
				}
				if(flag) {
					for(Node node : mine) {
						answer[node.x][node.y] = '*';
					}
				}

			}
		}
	}
	public static int findMine(int x,int y) {
		int mineCnt =0;
		for(int i=0;i<8;i++) {
			int nextX = x+dist[0][i];
			int nextY = y+dist[1][i];
			if(nextX<0 || nextX > N-1 || nextY<0 || nextY>N-1) continue;
			if(board[nextX][nextY]=='.') continue;
			mineCnt++;
		}
		return mineCnt;
	}

}