[JAVA] 백준 10711번: 모래성

사실 이 문제 예전에 풀었던 문제입니다.

처음 풀 때는 시간 초과 때문에 인터넷의 도움을 받았던 기억이 생생합니다.

 

 

그래도 예전에 푼 문제를 다시 풀 때는 언제나 긴장됩니다.

과연 성장했는가, 제자리인가 .. 

 

 

솔직 고백하자면  뿌듯해서 올리는 풀이글입니다.

저 이 문제 JAVA 기준 1등이에요 ✌🏻🎶💖

나보다 나은 사람 코드 훔쳐보려고 등수봤는데 감격해서 굳이 굳이 씁니다. 

 

---

풀이 (C++)

https://viin.tistory.com/152

[C++] 백준 10711번: 모래성

 

 

접근법은 기존과 똑같습니다. 단지 요즘은 Java를 공부 중이니 Java로 다시 풀었을 뿐..!

• 백준 코드 보기 : https://www.acmicpc.net/source/79638394

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

public class Main {

    public static void main(String[] args) throws IOException {

        final int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};
        final int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[][] grid = new int[H][W];
        Queue<int[]> q = new ArrayDeque<>();
        for(int i=0; i<H; ++i)
        {
            String line = br.readLine();
            for(int j=0; j<W; ++j)
            {
                char ch = line.charAt(j);
                if (ch == '.') q.offer(new int[]{i, j});
                else grid[i][j] = Character.getNumericValue(ch);
            }
        }

        int answer = 0;
        int[] front;
        while(!q.isEmpty())
        {
            int qSize = q.size();
            while(qSize-- > 0)
            {
                front = q.poll();

                for(int d=0; d<8; ++d)
                {
                    int x = front[0] + dx[d];
                    int y = front[1] + dy[d];

                    if((x<0 || y<0 || x>=H || y>=W)|| grid[x][y] == 0) continue;
                    if(--grid[x][y] == 0)
                        q.offer(new int[]{x, y});
                }
            }
            ++answer;
        }

        System.out.print(answer-1);
    }
}

 

 

시간을 줄이기 위해 나름 신경 썼던 부분

 

# 사용되는 부분이 많이 중복되지 않는다면 그냥 코드에 작성한다. 

예를 들어격자를 벗어나는걸 확인하는 메서드가 있습니다. 

그런데 이 메서드는 호출횟수가 굉장히 많고 사실상 if문 한줄만 가져오면 되므로 이번에는 굳이 함수로 작성하지 않았습니다. 

bool isValid(const int x, const int y)
{
    if(x<0 || x>=W || y<0 || y>=H)
        return false;

    return true;
}

 

 

# 필수가 아니라면 전역 변수를 지역 변수로 호출한다. 

평균적으로 전역이 접근할 때 시간이 더 걸리니 되도록이면 지역 변수를 사용했습니다. 

이번 문제에서는 위치를 방향을 저장하는 방향 배열도 지역으로 변경했습니다. 

const int dx[8] = {0, 0, 1, -1, -1, 1, 1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

 

+ 이래저래 필요없을 것 같은 변수들은 정리했습니다. 

 

-태희쌤 💙 이 수업 도중에 지나가듯이 말씀해주신 것인데 도움이 된 것 같아서 나중에 나를 위해서 작성-