초니로그

문제 링크 - https://softeer.ai/practice/6282

문제 설명

배열의 크기 n과 n*n의 배열값이 입력됨(0: 장애물X, 1: 장애물O)

좌측 최상단을 0,0으로 여기는 n*n의 2차원 배열을 탐색하며,

상하좌우로 연속된 장애물 구역의 총 개수와 각 장애물 구역 내의 장애물 개수를 오름차순으로 출력

풀이법 구상

기본 DFS/BFS를 통한 탐색 문제

코드 구현 (자바 사용)

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

public class Main {

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

        // 입력받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] map = new int[N][N];
        for(int i=0; i<N; i++) {
            char[] input = br.readLine().toCharArray();
            for(int j=0; j<N; j++) map[i][j] = Character.getNumericValue(input[j]);
        }
        
        // BFS를 활용한 블록 탐색
        ArrayList<Integer> block = new ArrayList<>();
        
        boolean[][] ch = new boolean[N][N]; // 방문 여부 확인용(방문O - true / 방문X - false)
        Queue<int[]> q = new LinkedList<>();
        
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};
        
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j] == 1 && !ch[i][j]) {
                    int cnt = 1; // 장애물 개수
                    q.offer(new int[]{i,j});
                    ch[i][j] = true;
                    while(!q.isEmpty()) {
                        int[] cur = q.poll();
                        for(int d=0; d<4; d++) {
                            int nx = cur[0] + dx[d];
                            int ny = cur[1] + dy[d];
                            
                            if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; // 지도 범위를 벗어난 경우
                            if(map[nx][ny] == 0) continue; // 도로인 경우
                            if(map[nx][ny] == 1 && ch[nx][ny]) continue; // 이미 방문한 장애물일 경우

                            q.offer(new int[]{nx,ny});
                            ch[nx][ny] = true;
                            cnt++;
                        }
                    }
                    block.add(cnt);
                }
            }
        }

        // 결과 출력
        Collections.sort(block);
        System.out.println(block.size());
        for(int b : block) System.out.println(b);
    }
}

코드 구현 (파이썬 사용)

def dfs(x,y):
    if x<0 or x>=n or y<0 or y>=n: return False
    if arr[x][y] == 1:
        sum.append(1)   # 연속된 구역 내 장애물 개수 +1
        arr[x][y] = 0   # 방문처리
        # 상하좌우 탐색
        dfs(x,y+1)
        dfs(x,y-1)
        dfs(x-1,y)
        dfs(x+1,y)
        return True
    return False
        

n = int(input())
arr = []
for _ in range(0,n): arr.append(list(map(int, input())))

sum = []  # 연속된 구역 내 장애물 개수를 추가할 배열
sum_arr = []
for p in range(0,n):
    for q in range(0,n):
        if dfs(p,q) == True: 
            sum_arr.append(len(sum)) # 연속된 하나의 구역을 탐색한 후, 구역 내 장애물 개수를 결과에 추가
            sum = []   # 새로운 연속된 구역 내 장애물 개수를 파악하기 위해 초기화

sum_arr.sort()
print(len(sum_arr))
for i in range(0,len(sum_arr)): print(sum_arr[i])

문제 링크 - https://www.acmicpc.net/problem/15649

문제 설명

n, m이 주어지면 1이상 n이하의 수 중 m개를 선택해 구성한 순열 출력

n >= m이며, n과 m 모두 1이상 8이하의 정수

풀이법 구상

파이썬을 사용하면 itertools 내 permutations 메소드를 써서 바로 풀이가 가능하지만 스위프트는 그런거 없음 왜..왜...

처음에는 1부터 n까지의 정수가 담긴 배열을 돌면서 하나씩 추가하고 배열에서 삭제해나가는 로직으로 생각했는데, 이러면 m중 반복문을 돌아야함 (그래도 시간복잡도가 O(N^m)이라 시간초과는 안 나겠지만 구현하기 까다로울 것 같아서 일단 포기)

1이상 n이하 정수 중에서 m개를 뽑는 방법은 DFS/BFS를 사용할 수 있는데

n이 4이고, m이 2인 경우를 생각해보면 1부터 4사이의 정수 중에 2개를 선택해야함

선택된 수를 담을 배열은 아래와 같은 경우의 수들을 가질 수 있음

[ ] -> [1] -> [1,2]

[ ] -> [1] -> [1,3]

[ ] -> [1] -> [1,4]

[ ] -> [2] -> [1,2]

[ ] -> [2] -> [2,3]

[ ] -> [2] -> [2,4]

...

[ ] -> [4] -> [3,4]

위 경우들은 트리로 시각화 할 수 있고, 각 노드들을 탐색하면서 노드를 구성하는 정수배열의 크기가 m인 경우만 중복없이 출력시키면 됨

는 그나마 익숙한 BFS로 구현했더니 시간초과

/// 시간초과난 코드

import Foundation

func solution(_ n: Int, _ m: Int) -> Void {
    var results: [[Int]] = []
    for i in 1...n { results.append([i]) }

    // 수열 생성
    for _ in 0..<m {
        for arr in results {
            var temp: [[Int]] = []
            for i in 1...n {
                if arr.contains(i) { continue }
                var temp_arr = arr
                temp_arr.append(i)
                temp.append(temp_arr)
            }
            
            for t in temp {
                if !results.contains(t) { results.append(t) }
            }
        }
    }

    // 사전 순으로 정렬
    var sorted_results: [[Int]] = []
    for arr in results { if (arr.count == m) { sorted_results.append(arr) } }
    
    sorted_results = sorted_results.sorted(by: { $0[0] < $1[0] })

    // 정답 출력
    for arr in sorted_results {
        var str = ""
        for a in arr { str += "\(a) " }
        print(str)
    }
}

let input = readLine()!.components(separatedBy: " ")
solution(Int(input[0])!, Int(input[1])!)

구글링했더니 대부분 백트래킹으로 풀었음

백트래킹은 DFS와 비슷하지만 DFS는 종료 조건만 가지고 무지성 재귀함수를 사용하고, 백트래킹은 답이 있을 것 같은 경우에만 탐색하는 것이 차이점임

백트래킹에서 쓰이는 '유망함', '유망하지않음', '가지치기'의 용어도 정답 존재 가능성과 연관된 것임

- 유망함 : 정답을 찾을 수 있는 가능성 O

- 유망하지않음 : 정답을 찾을 가능성 X

- 가지치기 : 유망하지 않은 경우를 제외하는 것

(아무튼 다시 이 문제로 돌아와서) BFS 풀이는 배열의 수가 0개 -> 1개 -> 2개 -> ... -> m개인 순서로 노드들을 탐색하기 때문에, 배열의 길이가 0개부터 m-1개인 탐색할 필요가 없는 경우까지 고려하게 됨

그리고 모든 결과 배열을 다 포함하고 마지막에 탐색하면서 길이가 m인 배열을 사전순으로 출력하기 위해 따로 정렬도 해줘야 함

근데 백트래킹 풀이는 가장 적은 숫자부터 구성된 배열 중, 길이가 m인 경우에만 출력하게 하면 되니까 불필요한 경우의 고려와 정렬 코드가 삭제될 수 있음

그럼 백트래킹을 쓰려면 뭐가 유망한 거고, 뭐가 유망하지 않은 건지를 알아야 하는데 n = 4, m = 2인 경우를 예시로 보면, 

결과배열이 [1]인 경우에는 1부터 4까지 중 1을 제외하고 추가해야함

이런 생각들로 아래처럼 구현하고 제출했더니 성공,,

코드 구현 (스위프트 사용)

import Foundation

func solution(_ n: Int, _ m: Int) -> Void {
    let temp:[Int] = []
    dfs(arr: temp, m: m, n: n)
}

func dfs(arr: [Int], m: Int, n: Int) -> Void {
    if (arr.count == m) {
        var str = ""
        for a in arr { str += "\(a) " }
        print(str)
        return
    }

    var temp = arr
    for p in 1...n {
        if !temp.contains(p) {
            temp.append(p)  // 1부터 n 사이의 배열에 없는 숫자 중 젤 작은 거 추가
            dfs(arr: temp, m: m, n: n)   // 위에서 숫자 새로 추가한 배열로 다시 검사
            temp.remove(at: temp.count-1)   // 위에서 검사 끝나고 오면 가장 최근에 추가했던거 삭제(그 자리에 다른 새로운거 넣어보려고)
        }
    }
}

let input = readLine()!.components(separatedBy: " ")
solution(Int(input[0])!, Int(input[1])!)

DFS/BFS로 풀 수 있을 것 같아도 시간 복잡도 한 번 더 고려해보고, 뭔가 될 것 같아서 풀었는데 시간초과나면 백트래킹 풀이도 고려해보자