초니로그

문제 링크 - 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://softeer.ai/practice/6255

문제 설명

암호화할 문자열(메세지)과 키값이 될 문자열(키)을 2줄에 걸쳐 입력받음

메세지를 아래와 같은 규칙을 적용하여 2글자씩 쌍으로 만듦

- 우선 2자씩 쪼갬 

- 같은 글자로 구성된 쌍은 사이에 'X'를 끼워주는데, 'XX'는 끼워줘봤자 여전히 중복이므로 'Q'를 끼워줌

- 가장 최종적으로 나온 쌍들 중 마지막이 1개 문자로 이루어졌다면 끝에 'X' 추가 (XX가 되어도 무관함)

각 쌍에 대해 입력받은 키값을 참고하여 다른 글자로 바꾸어줘야하는데, 참고할 키값은 길이와 상관없이 아래와 같은 규칙으로 5*5의 형태로 변형해야함

- 입력받은 키값을 차례로 돌면서 (0,0)자리부터 한 글자씩 채워줌

- 단, 이미 이전에 등장한 적이 있는 글자가 또 나오면 건너뜀

- 입력받은 키값을 이용해 채웠는데 25자리를 모두 채우지 못 한 경우, 알파벳 중 안 쓴 걸 가져다가 채우면 됨

풀이법 구상

문제가 아주 길어서 이해하는데 시간이 좀 걸렸음

문제를 풀어나갈 순서를 아래처럼 정리하면 크게 복잡한 논리를 요구하지는 않아보임

1. 메세지/키 입력받기
2. 2글자 쌍으로 나누기
3. 입력받은 키를 5*5의 형태로 변경
4. 쌍마다 암호화
   (1) 암호판의 같은 행에 존재하는 쌍이면 우측 한 칸씩 밀어서
   (2) 같은 행에 존재하지 않고 같은 열에 존재하면 아래로 한 칸씩 밀어서
   (3) 서로 다른 행/열에 존재하는 경우 서로의 열값을 바꾼 위치로

코드 구현 (파이썬 사용)

### 중복되는 글자쌍이 없도록 메세지 수정하는 메소드
def getPair(input):
    # 우선 2자씩 쪼개서 확인
    # 같은 글자로 구성된 쌍은 사이에 'X'를 끼워주는데, 글자쌍이 'XX'인 경우에는 'Q'추가
    # 가장 최종적으로 나온 쌍들 중 마지막이 1개 문자로 이루어졌다면 끝에 'X' 추가 (XX가 되어도 무관함)
    result = input
    while isDuplicated(result): result = setNotDuplicated(result)  # 중복되는 쌍이 없을 때까지 반복
    if len(result)%2 == 1: result += 'X'
    return result

### 중복되는 글자쌍이 존재하는지 확인하는 메소드
def isDuplicated(str):
    for i in range(0,len(str)-1,2):
        if str[i] == str[i+1]: return True
    return False

### 중복되는 글자쌍 사이에 'X' 혹은 'Q'를 추가하는 메소드
def setNotDuplicated(str):
    str_list = list(str)
    for i in range(0,len(str)-1,2):
        if str_list[i] == str_list[i+1]:
            str_list.insert(i+1, 'X' if str_list[i] != 'X' else 'Q')
            return ''.join(str_list)

### 입력된 키값을 기반으로 5*5 크기의 암호판을 만드는 메소드
def getKey(input_key):
    # 입력받은 키값을 차례로 돌면서 (0,0)자리부터 한 글자씩 채워줌
    # 단, 이미 이전에 등장한 적이 있는 글자가 또 나오면 건너뜀
    # 입력받은 키값을 이용해 채웠는데 25자리를 모두 채우지 못 한 경우, 알파벳 중 안 쓴 걸 가져다가 채우면 됨
    alphabet_list = [chr(i) for i in range(ord('A'),ord('Z')+1)]
    alphabet_list.remove('J')
    key_arr = []
    # 우선 입력받은 키값으로 배열 채우기
    for k in input_key:
        if len(key_arr) == 25: break
        if k in alphabet_list:
            key_arr.append(k)
            alphabet_list.remove(k)
    
    # 배열 길이가 25 미만이면 안 쓴 알파벳 사용
    if len(key_arr) < 25:
        for a in alphabet_list:
            if len(key_arr) == 25: break
            key_arr.append(a)

    # 1차원 배열 값을 토대로 2차원 암호판 구성 후 반환
    # result_key = [[0] * 5] * 5 # 얕은 복사로 인해 값 변경에 오류 발생
    result_key = [[0 for p in range(5)] for q in range(5)]
    for p in range(0,5):
        for q in range(0,5): result_key[p][q] = key_arr[(5*p)+q]

    return result_key
            
    

### 수정된 메세지의 글자쌍에 대해 키를 이용하여 암호화하는 메소드
def getResultMsg(pairs, key):
    # case 1) 암호판의 같은 행에 존재하는 쌍이면 우측 한 칸씩 밀어서
    # case 2) 같은 행에 존재하지 않고 같은 열에 존재하면 아래로 한 칸씩 밀어서
    # case 3) 서로 다른 행/열에 존재하는 경우 서로의 열값을 바꾼 위치로
    pair_arr = []
    for i in range(0,len(pairs)-1,2):
        pair_arr.append(pairs[i]+pairs[i+1])

    result = ''
    for pair in pair_arr:
        result += getModifiedKey(pair, key)

    print(result)


def getModifiedKey(pair, key):
    location = [
        [-1, -1],  # 첫번째 글자의 위치
        [-1, -1]   # 두번째 글자의 위치
    ]

    for p in range(0,5):
        for q in range(0,5):
            if pair[0] == key[p][q]: 
                location[0][0] = p 
                location[0][1] = q
            if pair[1] == key[p][q]: 
                location[1][0] = p 
                location[1][1] = q

    if location[0][0] == location[1][0]: 
        # case 1) 암호판의 같은 행에 존재하는 쌍이면 우측 한 칸씩 밀어서
        location[0][1] = (location[0][1] + 1)%5
        location[1][1] = (location[1][1] + 1)%5
        
    elif location[0][1] == location[1][1]: 
        # case 2) 같은 행에 존재하지 않고 같은 열에 존재하면 아래로 한 칸씩 밀어서
        location[0][0] = (location[0][0] + 1)%5
        location[1][0] = (location[1][0] + 1)%5
        
    else: 
        # case 3) 서로 다른 행/열에 존재하는 경우 서로의 열값을 바꾼 위치로
        temp = location[0][1]
        location[0][1] = location[1][1]
        location[1][1] = temp
    
    return (key[location[0][0]][location[0][1]] + key[location[1][0]][location[1][1]])

# 1. 메세지/키 입력받기
msg_input = input()
key_input = input()

# 2. 2글자 쌍으로 나누기
pairs = getPair(msg_input)

# 3. 입력받은 키를 5*5의 형태로 변경
key = getKey(key_input)

# 4. 쌍마다 암호화
getResultMsg(pairs, key)

이 문제 1시간 안에 풀라 그러면 눈물닦는데 10분은 걸릴 듯;