[softeer] 6282

문제

 

 

 

메모리 제약

 

제약사항

 

 

입/출력

 

문제 분석

처음 문제를 보자마자 DFS 를 쓰면 될 것 같다는 생각이 들었다.
다만... 뚜렷한 방법이 생각나지 않아서 각 행,열 로 이중포문을 돌면서 왼쪽, 윗쪽을 체크하는 방식으로 하기로 했다.

 

 

풀이 1

import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
//        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // https://softeer.ai/practice/6282

        /*
            * 장애물 배열 생성
            *
            * 1-1. 입력값이 0이다.
                * 2-1. 왼쪽 or 위에 값이 장애물이다
                * 2-2. 왼쪽 or 위에 값이 장애물이 아니다.
                * => 새로운 값
            * 1-2. 입력값이 1이다.
         */
        int obstacleCount = 0;
        ArrayList<int[]> obstacles = new ArrayList<>();

        int[][] inputs = {{1,1,1,0,1,1,1}, {0,1,1,0,1,0,1},{0,1,1,0,1,0,1}, {0,0,0,0,1,0,0}
                ,{0,1,1,0,0,0,0},{0,1,1,1,1,1,0},{0,1,1,0,0,0,0}};

        for (int i= 0; i < inputs.length; i++) {
            for (int j= 0; j < inputs[i].length; j++) {
                if (inputs[i][j] == 0) { // 현재 값이 장애물이 아니다.
                    continue;
                } else { // 현재 값이 장애물이다.
                    // 왼쪽만 체크
                    if (i == 0) {
                        // 위에도 0인경우
                        if (j == 0) {
                            obstacleCount += 1;
                        } else {
                            // 왼쪽 체크
                            if (inputs[i][j-1] == 0) {
                                obstacleCount += 1;
                            }
                        }
                    } else {
                        if (j == 0) {
                            // 위 체크
                            if (inputs[i-1][j] == 0) {
                                obstacleCount += 1;
                            }
                        } else {
                            if (inputs[i-1][j] == 0 && inputs[i][j-1] == 0) {
                                obstacleCount += 1;
                            }
                        }

                    }
                }
            }
        }
        System.out.println(obstacleCount);


    }

}

 

 

실패

위 코드는 "장애물별 갯수 출력"을 풀지 않아서 제출하지 않았지만, 해당 과정이 들어가면 매우 복잡해질 것 같다는 생각이 들었다.

그래서 다시 처음부터 DFS 방식으로 체크하는 방식으로 고치기로 하였다...
알고리즘 문제는 어려운걸 풀어도 아직 너무 어렵다..

 

풀이

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

public class Main {

    static int count; //
    static List obstacles = new ArrayList<>(); // 장애물 개수
    static boolean[][] visitYn; // 방문 여부
    static int[][] inputs;

    public static void main(String[] args) throws IOException {
        // https://softeer.ai/practice/6282

        /*
            * DFS 문제가 맞았음.
            * 상하좌우로 찾는다는건 알았는데, 제일 중요한 사항을 간과했음.
            * 1인 곳을 가게되면 모두 걸리는데 그걸 방지하기위해서 방문한 곳을 체크하는 배열을 만들어야하는 것이었음.
            * 또한, 배열 자체를 돌리는게 아니라 맵 크기의 변수를 돌림으로서 배열과 다른 값으로 작업
            *
         */

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int mapSize = Integer.parseInt(bf.readLine());
        // 입려값 초기화
        inputs = new int[mapSize][mapSize];

        for (int i = 0; i < mapSize; i++) {
            int[] inputRow = Arrays.stream(bf.readLine().split("")).mapToInt(Integer::new).toArray();
            inputs[i] = inputRow;
        }

        visitYn = new boolean[mapSize][mapSize];

        // 초기화
        for (int i = 0; i < mapSize; i++) {
            for (int j = 0; j < mapSize; j++) {
                visitYn[i][j] = false;
            }
        }

        // dfs 처리
        for (int i = 0; i < mapSize; i++) {
            for (int j = 0; j < mapSize; j++) {
                count = 0;
                if (dfs(i, j, mapSize) == true) { // 해당 값이 장애물 블록인경우
                    obstacles.add(count);
                }
            }
        }

        System.out.println(obstacles.size());
        Collections.sort(obstacles);
        for (int i = 0; i < obstacles.size(); i++) {
            System.out.println(obstacles.get(i));
        }
    }

    public static boolean dfs(int x, int y, int mapSize) {
        // 범위를 벗어나면 out
        if (x <= -1 || x >= mapSize || y <= -1 || y >= mapSize) {
            return false;
        }

        // 장애물이고 방문하지 않은 경우
        if (inputs[x][y] == 1 && !visitYn[x][y]) {
            count += 1;

            //방문처리
            visitYn[x][y] = true;

            // 상하좌우 처리
            dfs(x-1, y, mapSize);
            dfs(x, y-1, mapSize);
            dfs(x+1, y, mapSize);
            dfs(x, y+1, mapSize);
            return true;
        }

        return false;
    }
}

 

 

성공

 

링크

https://softeer.ai/practice/6282

Softeer - 현대자동차그룹 SW인재확보플랫폼