Red-Black Tree 속성/검색/삽입/삭제, 시간복잡도

1. Red-Black Tree

 이진트리 중 Binary Search Tree인 경우에는 한쪽에만 노드들이 치우쳐 있어 균형잡힌 트리가 만들어지지 않을 수 있다. 그렇다면 탐색을 하기 위한 시간이 늘어나게 되는 단점이 있는데, 이를 보완하여 균형잡힌 트리를 만들고자 만들어진 자료구조가 Red-Black Tree라는 것이다.

---

2. Red-Black Tree 정보

Red-Black Tree는 각 노드의 색깔을 red, black 중에 선택하여, 주어진 조건을 만족시켰을 때 성립하는 Tree이다.
Red-Black Tree의 성립조건은 다음과 같다.
 

1. 루트 노드는 언제나 Black이다.

1. Leaf 노드 (말단 노드) 또한 언제나 Black이다.

1. 만약 노드가 Red라면, 그 노드의 자식들은 언제나 Black이다. 즉, red node가 연속으로 올 수 없다.

1. 루트에서 말단 노드까지의 Black node의 개수는 언제나 동일하다. 

 Red-Black Tree의 예시, 출처: wikipedia

위 그림이 Red-Black tree의 예시라고 할 수 있다. 여기서 NIL은 말단 노드를 뜻하고 위의 그림을 보면 red black tree의 property를 모두 만족시켰다는 것을 잘 알 수 있다. 그러면 이제 Red-Black Tree에서의 검색, 삽입, 삭제를 어떻게 구현하는지 살펴보자. 

---

1. 검색

Red-Black Tree에서의 검색은 일반 Binary Search Tree에서의 검색과 동일하다. 만약 parent node보다 찾으려는 숫자가 작다면 왼쪽 child node로 이동해주고, 숫자가 크다면 오른쪽 child node로 이동해주면 된다. 
검색의 경우는 Red-Black Property가 존재한다고 해서 달라지는 부분이 없기 때문에 삽입과 삭제에 집중해보자.

---

2. 삽입 (Insertion) 

먼저 노드를 삽입하려고 하면 그 노드의 색깔을 정해주어야 한다. 우리는 Red-Black Tree에서 삽입할 노드는 무조건 Red라고 가정하고 시작한다. 
여기서 아무 문제없이 삽입이 잘 되는 경우는 삽입하려고 하는 노드의 부모 노드의 색깔이 black일 경우이다. 왜냐하면 Red-Black property 3번에 의해 Red 위에 Red가 나올 수 없기 때문에 Red 위의 부모 노드가 Black일 경우에는 아무런 추가 조치 없이 삽입이 가능해진다. 
 

삽입에서 문제가 없는 경우

즉 위와 같은 그림에서는 전혀 문제가 되지 않는다. 여기서 하얀색으로 표현한 것은 상황에 따라 Red/Black이 되는 경우인데 Red/Black으로 칠해진 노드만 집중해서 보기 위해서 다른 노드는 하얀색으로 표현해놓았다.
 
하지만 문제가 되는 경우는 삽입하려는 부모의 노드가 빨간색일 경우이다. 

삽입에서 문제가 되는 경우

위 그림처럼 Red node가 연속으로 오게 된다면 Red-Black Property 3번을 충족시키지 못한다. 따라서 이 경우에는 추가적인 조치가 필요하다. 
 
이를 위해 우리는 경우를 몇 가지로 나누어볼 수 있다. 

기본골격

위와 같은 기본 구조에서 p와 대칭점에 있는 노드를 우리는 s라고 부를 것이다. sibiling, 형제노드의 약자이다. s 노드가 Red냐 Black이냐에 따라서 삽입의 조정 방법이 달라진다. 
 

s가 Red일 경우 

• 먼저 s가 Red일 경우부터 살펴보겠다.

s가 Red일 경우

위 그림처럼 생각해볼 수 있는데 이 경우에는 아래처럼 바꾸어주면 된다.

 

즉 p와 s 노드를 둘 다 Black으로 바꾸어 주고 P의 parent node를 red로 바꾸어주는 것이다. 하지만 만약 p^2의 parent node 또한 red 였다면 추가적으로 문제가 생긴다. 이 경우에는 p^2 노드를 recursive하게 하여 추가적인 조정을 해주어야 한다. 

 

• 다음으로 만약 s 노드는 Black이고 추가하려는 x 노드가 p의 left child일 경우를 살펴보자

즉, 위와 같은 경우라고 볼 수 있다. 이런 경우에는 아래의 그림처럼 조정해주면 된다. 

즉 p 노드를 중심으로 right rotate를 시키고 p 노드의 색깔을 red 에서 black으로 바꾸어주면 되는 것이다. 

 

• 마지막으로 s 노드가 black이면서 x는 p의 right child인 경우를 살펴보자

위 그림과 같은 경우를 의미한다. 이 경우에는 아래와 같이 변경해주면 된다.

하지만 이런 식으로 변경해도 x과 p가 연속적으로 red가 나타났기 때문에 문제가 된다. 하지만 이 경우는 위에서 s 노드가 black이고 새로운 노드가 left child 인 경우에 해당되기 때문에 두번째 경우로 이동해서 추가적으로 처리해주면 된다. 

 

---

3. 삭제

다음으로는 조금 더 까다로운 Red-Black Tree에서의 삭제를 알아보겠다. 

만약 삭제하려는 노드가 Red면 그 노드만 삭제해주면 되고, Black이더라도 child node가 Red라면 해당 노드를 삭제해주고 child의 색깔을 Black으로 바꿔주면 아무 문제가 없다. 

 

문제가 되는 경우는 삭제하려는 노드와 그 자식 노드의 색깔이 모두 다 Black일 경우이다. 왜냐하면 Red-Black tree property 4번에 의해 leaf 노드까지의 black node의 개수는 모두 일정해야 하기 때문이다. 하지만 Black 노드를 하나 삭제해 버린다면 그러한 property가 깨지기 때문에 문제가 생기는 것이다. 그래서 삭제의 경우에도 몇 가지 경우를 나누어보겠다. 

 

아래 그림에서 x 노드는 Black인 노드 m을 삭제하고 난 이후의 child node를 의미하게 된다. 하지만 Black node의 개수가 하나 모자라기 때문에 옆에 -1로 표시하겠다. 

 

Case 1.

삭제한 이후의 검정색 노드가 하나 모자라는 노드를 x로 표시했을 때 위와 같은 그림이 case 1이다. s 는 Black이고 s의 left child와 right child 노드가 모두 Black인 경우다. 이 경우는 가장 간단한 경우로 아래와 같이 조정해주면 된다.

 

위와 같이 조정해주면 p 노드가 Black으로 바뀌면서 x 노드까지의 경로에 모자랐던 black 노드의 개수를 하나 늘려줌으로써 문제가 해결된다. 

 

case 2.

case1과 유사하지만 이번에는 p 노드까지 모두 다 Black이다. 

이번에도 s 노드를 Red로 바꾸어주지만 Black 노드가 하나 부족한 것이 p node로 전이되었다고 할 수 있다. 그러므로 여기서는 p 노드를 문제 노드로 놓고 재귀적으로 또 문제를 해결해주어야 한다. 

 

case 3. 

s 노드는 black이고 r node가 red인 경우를 뜻한다. 여기서도 마찬가지로 하얀색 노드는 red/black이 와도 괜찮다는 뜻이며 red/black 각각의 경우에 대해 대입해보면 된다. 여기서는 묶어서 한 가지 상황으로 처리한 것이다. 이 경우에는 아래의 그림과 같이 left rotate를 시켜주면 된다. 

 

여기서 하얀색 노드는 이전의 색깔을 그대로 따라간다는 의미이다. 

 

case 4. 

이번에는 위와 반대로 r이 Black이고 L이 red인 경우이다. 이 경우에는 아래와 같이 rotate를 시켜준다. (s를 기준으로 하고 rotate를 시켜주는 것임)

하지만 위와 같이 변경하여도 x에 여전히 -1이 있는 것을 볼 수 있을 것이다. 하지만 이 경우에는 이제 rotate를 시켰으므로 case 3으로 이동할 수 있다는 것을 알 수 있다. case 3으로 가서 똑같이 한번 더 조정을 해주어야 한다.

 

case 5.

마지막 케이스다. 마지막 케이스는 s node가 red 인 경우이다. 이 경우에는 아래와 같이 조정하며 위의 케이스들 중의 하나로 다시 이동하게 된다. 

 

---

3. Red-Black Tree 시간복잡도

검색의 시간복잡도: O(logn) 균형잡힌 트리이기 때문

삽입의 시간복잡도: O(logn) 계속 재귀적으로 호출하면서 루트까지 올라갈 수 있기 때문

삭제의 시간복잡도: O(logn) 계속 재귀적으로 호출하면서 루트까지 올라갈 수 있기 때문

[유튜브 동영상 편집] 다빈치 리졸브 편집 기본기능 + 동영상 끌어오기

1. 다빈치 리졸브 프로그램 동영상 추가

 다빈치 리졸브 프로그램을 시작하고 동영상을 추가하는 과정까지 설명을 해보도록 하겠다.

먼저 프로그램을 실행해준다.

---

그러면 하단에

 

 

위와 같은 버튼 세개가 있을텐데 이중에서 New Project를 클릭해서 새로운 프로젝트 파일을 생성해준다.

 

프로젝트 이름 생성

위와 같이 그러면 Create New Project라는 새로운 창이 뜰텐데 여기에 파일 제목을 생성하고 Create 버튼을 눌러준다. 참고로 여기 파일 제목은 유튜브 제목과는 무관하니 편한대로 설정해주면 된다.

 

---

동영상 가져오기 루트

다음으로는 동영상을 가져와야 한다. File -->  Import File --> Import Media를 눌러주면 내 기기에 있는 동영상 파일을 가져올 수 있다. 나는 구글드라이브에 업로드해서 가져오고 있다.

---

 

그렇게 해서 원하는 파일을 클릭하게 되면,

frame rate

 

위와 같이 새로운 창이 뜰때가 있는데 프레임 속도를 맞춰주겠다는 것이므로 change를 클릭해주면 된다. 

 

그러면

 

Media Pool 예시

위와 같이 Media Pool이라는 부분 아래 원하는 동영상이 들어간 것을 알 수 있다. 

 

---

다음으로 동영상을 원하는 트랙에 가져다 넣어야 하는데,

cut -> edit

 

그러기 위해서 다빈치 리졸브 하단부에 보면 위 그림처럼 버튼을 볼 수 있다. 여기서 편집을 위해서는 Cut 탭에서 Edit 탭으로 바꾸어주자. Edit 탭을 클릭해주면 된다.

---

다음으로 Edit 페이지가 나왔다면

동영상 끌어오기 예시

위와 같이 동영상을 타임라인 부분에다가 끌어다가 가져오자. 

그러면 위와 같이 video, audio 트랙이 생길 것이다. 

만약 audio 가 없는 영상이라면 audio 트랙에는 아무것도 들어가지 않을 것이다.

---

만약 추가로 음악을 넣고 싶다면 audio 트랙에 음악 파일을 끌어다가 넣어주면 된다. audio 파일도 동영상을 가져온 것처럼 똑같이 File -> Import File-> Import Media에 들어가서 가져와 주면 Media Pool에 등록된 것을 볼 수 있을 것이다.

---

자막을 넣고 동영상을 자르는 것은 다음 포스팅에서 다루어보도록 하겠다.

네트워크에서 protocol 프로토콜이란?

protocol이란? 

protocol이란 한 마디로 통신에서 데이터를 주고받는데 있어서의 일종의 규약이라고 할 수 있다. 

 

사람 사이에서도 human protocol이 존재한다. 간단한 예시로 인사를 건네면 인사가 돌아오는 등의 형식을 기대할 수 있다. 이와 비슷하게 protocol을 네트워크에서도 적용할 수 있다. 여기서 말하는 protocol은 기계 사이에 규약이라고 할 수 있다. 매체로만 연결되어 있는 두 device 사이에 의도를 메시지와 함께 보내야 한다. 예를 들어, 이 디바이스가 다른 디바이스에게 파일을 넘겨달라고 할 때 connection request를 보내고 이후 connection response를 받게 된다. 그러면 그 때 get이라는 명령어를 통해 파일에 대한 정보를 주면서 다시 메시지를 보내면 file을 받을 수 있는 형식이다. 이런 식으로 정해놓은 룰을 통신 protocol이라고 하는 것이다.

 

인터넷 상에서 일어나는 모든 communication activity는 철저히 protocol에 의해서 관리되고 관장되는 것이다. 네트워크 사이에서 주거니 받거니 하는 메시지 형태, 양식을 정하기, 포맷을 정하기, 순서를 정하기, 메시지를 받고 나서 다음에 취해야 하는 action이 무엇인가 등등을 철저히 정하는 것이 protocol이라고 할 수 있다. 

 

다시 말해, protocol은 두 개 이상의 entity 사이의 데이터 교환을 전체적으로 관장하는 규칙들의 set이라고 볼 수 있다. 따라서 데이터 교환을 해야 하기 때문에 같은 언어로 통신을 해야 한다.

---

 

protocol의 요소

 

1. syntax : 

메세지들의 포맷, 길이, 그 안에 들어가 있는 데이터의 내용 등을 포함

 

2. semantics: 

메세지들의 의미. 메세지의 의미에 따라서 취해지는 액션이 달라지고 이에 따라 응답해야 하는 이벤트들도 달라진다. 이렇게 메세지의 의미와 그에 따라 취해야 하는 액션을 정의한 것이 semantics 요소에 포함된다.

 

3. timing: 

메세지를 언제 버릴지, 언제 재전송을 해야 하는지 등의 시간을 결정하는 것이 timing 요소이다.

 

---

이렇게 protocol은 통신을 원할하게 만들기 위한 상호 rule이기 때문에 통신에서 가장 중요한 개념이라고 해도 무방하다. 

 

표준 구축

 

그러면 이러한 protocol은 누가 만드는 것일까? 분명 rule이기 때문에 표준이 필요할 것이다. 우리가 익숙한 TCP, IP, HTTP, Skype, 802.II 모두 이러한 표준의 대표적인 예시이다. 그렇기 때문에 protocol은 이러한 규칙을 표준화시키는 국제기구가 존재한다. 인터넷 표준 단체는 IETF (Internet Engineering Task Force) 라고 한다. 여기서 인터넷 관련 모든 protocol을 표준화시키면서 개정하는 것이다. 

protocol을 정할때는 모두가 모여서 표준화시키는 것이 아니라 각자 자신의 protocol을 제출해 자기것이 얼마나 좋은지에 대한 설득을 하는 과정을 거친다고 한다. RFC (Request for comment) 는 비평을 기다리는 문서라는 뜻으로, 컴퓨터과학자들은 RFC 메모의 형태로 생각을 출판하게 된다. IETF는 일부 RFC를 표준으로 지정하기도 하며 'RFC 몇번' 이런 식으로 표준을 발표한다. 

 

Cellular network은 인터넷 쪽에서 만드는 것이 아니라 3GPP(3rd generation partnership project)에서 표준화한다.

LAN은 802.11위원회에서 표준화시켜서 거기서 나오는 모든 표준화 protocol은이 위원회에서 만든 LAN protocol이 돌아가고 있다.

인터넷을 바라보는 두 가지 관점

인터넷을 바라보는 두 가지 관점

1) 첫 번째 관점: 네트워크의 네트워크

첫 번째 관점은 인터넷은 네트워크의 네트워크라는 것이다. 이는 구성 component 들로 인터넷을 바라본 것이고,

앞서

https://www.programmingstory.com/2024/05/10.html

위 포스팅에서 다루었던 내용이 이 관점에 해당한다. 

---

2. 두 번째 관점: service view

인터넷을 바라보는 두 번째 관점은 service view이다. 그냥 사용자어플리케이션에게 전달 서비스를 제공하는 기반시설이다라는 관점인 것이다. 인터넷, 컴퓨터네트워크, 서로 멀리 떨어져있는 두 컴퓨터 사이에서 돌아가는 어플리케이션 프로그램에 전달 서비스를 제공해주는 인프라, 기반시설이다라는 관점으로 볼 수 있다.

 

또한 이 관점에서는 앱들에게 programming interface를 제공하는 기능정도로 생각하면 된다. 즉 API (Application Program Interface)를 제공하는 관점으로 볼 수 있다. 사용자의 입장에서는 네트워크의 구성요소는 별로 관심이 없다. 사용자 입장에서는 컴퓨터 시스템 내에서 데이터를 읽고 쓰는 것처럼 그것을 불러서 쓸 수 있는 것이다. 

 

즉 인터넷을 바라보는 두 번째 관점 service view는 철저히 사용자의 입장에서 생각한 관점이라고 할 수 있다. 

[백준] 1600번 말이 되고픈 원숭이 문제 BFS로 풀어보기

1. 문제

www.acmicpc.net/problem/1600

문제의 입력, 출력, 더 자세한 instruction은 위 백준 링크에서 확인하고 오늘은 1600번 풀이법에 대해 알아보도록 하자.

---

2. BFS 개념

대표적으로 BFS를 사용할 수 있는 문제이다.

https://www.programmingstory.com/2024/02/dfs-bfs.html

BFS에 대해 익숙하지 않다면 위의 개념을 먼저 보고 오는 것을 추천한다.

---

3. 풀이

BFS에 관한 전형적인 문제인데 하나 변형된 부분이 있다. 바로 k번만 특수하게 움직일 수 있다는 것이다. 우리는 그동안 BFS를 풀 때 2차원 배열을 사용하여 행의 좌표, 열의 좌표를 사용하였다. 하지만 이 경우에는 k번만 특수하게 움직일 수 있으니 그동안 얼만큼 움직였는지를 별도로 기록할 필요가 있다. 

 

따라서 이번에는 3차원 배열을 만들어야 한다. 그리고 이동할 수 있는 방향도 총 12가지로 늘어난다. 예전에는 4가지가 대부분이었는데 이번에는 k번 이하로 대각선 방향도 움직일 수 있는 자유가 주어진다.

 

그래서 이번에는 

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

이런식으로 static 변수들을 가져온다. dx와 dy모두 이동할 수 있는 방향을 뜻하고 used 라는 배열은 대각선으로 이동할 경우에 k번 중에 1번을 쓰는 것이므로 이런 식으로 하나의 배열을 더 준비했다.

---

처음에는 모든 d 배열을 -1로 초기화를 한 뒤에 만약 해당 d 배열의 값이 -1이라면 아직 방문하지 않았다는 뜻이므로 +1을 해준다. 이 문제에서는 인자가 세개가 필요하다는 것을 알 수 있을 것이다. 대각선 방향으로 몇 번 움직였는지의 회수도 queue에 함께 넣어주고 이것이 문제에서 입력받은 횟수보다 작거나 같은지를 확인해주어야 한다. 

 

이후 이 문제의 답은 d[n-1][m-1][k] 에 있다고 생각하면 잘못된 것이다. 문제에서 분명히 k 이하라고 했기 때문에 우리는 k의 값을 0부터 k까지 모두 다 검사하면서 최소값을 찾아야 하는 것이다. 

3. 코드

 

import java.util.*;

public class Main{
     static final int[] dx = {0,0,1,-1,-2,-1,1,2,2,1,-1,-2};
    static final int[] dy = {1,-1,0,0,1,2,2,1,-1,-2,-2,-1};
    static final int[] used = {0,0,0,0,1,1,1,1,1,1,1,1};
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int l = sc.nextInt();
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] a = new int[n][m];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int[][][] d = new int[n][m][l+1];
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                Arrays.fill(d[i][j],-1);
            }
        }
        Queue<Integer> q=new LinkedList<>();
        q.add(0); q.add(0); q.add(0);
        d[0][0][0]=0;
        while(!q.isEmpty()){
            int x=q.remove();
            int y=q.remove();
            int c=q.remove();
            for(int k=0; k<12; k++){
                int nx=x+dx[k];
                int ny=y+dy[k];
                int nc=c+used[k];
                if (nx>=0 && nx<n &&ny>=0 &&ny<m && nc<=l){
                    if (a[nx][ny]!=1){
                        if (d[nx][ny][nc]==-1){
                            d[nx][ny][nc]=d[x][y][c]+1;
                            q.add(nx);
                            q.add(ny);
                            q.add(nc);
                        }
                    }
                }
            }
        }
        int ans = -1;
        for (int i=0; i<=l; i++) {
            if (d[n-1][m-1][i] != -1){
                if (ans == -1 || ans > d[n-1][m-1][i]) {
                ans = d[n-1][m-1][i];
            }
            } 
            
        }
        System.out.print(ans);
    }
}

이렇게 변형문제가 있을 수 있으니 잘 연습해두자.

[백준] 17141번 연구소2 문제 BFS로 풀어보기

1. 문제

 www.acmicpc.net/problem/17141

자세한 문제의 사항은 위의 링크를 클릭하여 백준 사이트에서 확인해보자.

---

2. 풀이

먼저 이 문제에서는 바이러스를 최대 m개 놓을 수 있기 때문에 어떤 위치에 바이러스 m개를 배치할지를 결정해주어야 한다. 그러기 위해서 먼저 문제에서 2라고 표시된 부분에 바이러스를 놓을 수 있다고 했기 때문에 가능한 바이러스의 위치를 ArrayList에다 넣어주도록 하겠다 (나는 virus라는 이름의 ArrayList를 만들어주었다). 그런 다음에 2라고 표시된 부분은 벽이 아니므로 자유롭게 움직일 수 있기에, 다시 0으로 바꾸어준다. 이러면 바이러스 자리인지 빈칸 자리인지 구분이 되지 않지만 우리는 ArrayList에다 넣어주었기 때문에 문제가 없다. 

 

다음으로 m개의 바이러스 자리를 결정하기 위해서 재귀함수를 사용해준다.

static void recur(int index, int cnt) {
        if (index == virus.size()) { 
            if (cnt == m) {//m개를 다 결정한 경우 
                bfs();
            }
        } else {
            int x = virus.get(index).x;
            int y = virus.get(index).y;
            a[x][y] = 3;
            recur(index+1, cnt+1); //해당 배열의 위치에 바이러스를 놓기로 결정한 경우
            a[x][y] = 0;
            recur(index+1, cnt);//해당 배열의 위치에 바이러스를 놓지 않기로 결정한 경우
        }
    }

위와 같은 재귀함수를 만들어주었다. 이런 식으로 재귀함수로 바이러스 m개의 위치를 결정해준다. 만약 마지막 바이러스의 위치에 도착했는데 cnt가 m개라면 m개의 바이러스 위치를 모두 결정해준 것이니 bfs 함수를 호출해주면 된다. 

 

여기서 바이러스의 진짜 위치를 표시해주기 위해서 만약 해당 좌표에 바이러스가 놓인 것이라면 그 값을 3으로 바꾸어주는 추가 작업도 실시해준다.

---

이제 그러면 bfs 함수가 어떻게 구성되어있는지 보도록 하겠다. (variable이 헷갈린다면 먼저 이 글의 가장 하단의 전체 코드를 보고 오는 것이 더 이해가 빠를 수 있다 )

static void bfs() {
        for (int i=0; i<n; i++) {
            for(int j=0; j<n; j++){
                d[i][j]=-1;
            }
        }
        Queue<Pair> q = new LinkedList<>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 3) {
                    q.add(new Pair(i,j));
                    d[i][j] = 0;
                }
            }
        }
        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (a[nx][ny] != 1 && d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        q.add(new Pair(nx, ny));
                    }
                }
            }
        }
        int cur = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] != 1) {
                    if (d[i][j] == -1) return;
                    if (cur < d[i][j]) cur = d[i][j];
                }
            }
        }
        if (ans == -1 || ans > cur) {
            ans = cur;
        }
    }

먼저 d라는 배열을 모두 -1로 초기화해준다. 그런 다음 바이러스의 위치를 모두 queue에다가 넣어준다. 만약 벽이 아니고 방문하지 않은 칸이라면 이를 다시 queue에 넣어두는 등 일반적으로 우리가 BFS를 구할 때 하는 행동을 해준다. 

 

그런 다음에 d의 최댓값을 찾는 것이 사실상 이 문제에서 구하고자 하는 값이다. 따라서 모든 배열의 칸을 돌면서 현재의 ans가 iteration에서 돌아서 나온 최댓값보다 작다면 이를 새로 update시키는 과정을 거친다. 

 

이렇게 모든 과정을 거치게 되면 우리는 문제에서 구하고자 하는 값을 얻을 수 있다. 아래는 Java로 구현한 전체 코드이다.

3. 코드

---

import java.util.*;
class Pair {
    int x, y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int[][] a;
    static int[][] d;
    static final int[] dx = {0,0,1,-1};
    static final int[] dy = {1,-1,0,0};
    static int n, m;
    static ArrayList<Pair> virus = new ArrayList<>();
    static int ans = -1;
    static void bfs() {
        for (int i=0; i<n; i++) {
            for(int j=0; j<n; j++){
                d[i][j]=-1;
            }
        }
        Queue<Pair> q = new LinkedList<>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] == 3) {
                    q.add(new Pair(i,j));
                    d[i][j] = 0;
                }
            }
        }
        while (!q.isEmpty()) {
            Pair p = q.remove();
            int x = p.x;
            int y = p.y;
            for (int k=0; k<4; k++) {
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (a[nx][ny] != 1 && d[nx][ny] == -1) {
                        d[nx][ny] = d[x][y] + 1;
                        q.add(new Pair(nx, ny));
                    }
                }
            }
        }
        int cur = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (a[i][j] != 1) {
                    if (d[i][j] == -1) return;
                    if (cur < d[i][j]) cur = d[i][j];
                }
            }
        }
        if (ans == -1 || ans > cur) {
            ans = cur;
        }
    }
    static void recur(int index, int cnt) {
        if (index == virus.size()) {
            if (cnt == m) {
                bfs();
            }
        } else {
            int x = virus.get(index).x;
            int y = virus.get(index).y;
            a[x][y] = 3;
            recur(index+1, cnt+1);
            a[x][y] = 0;
            recur(index+1, cnt);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new int[n][n];
        d = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
                if (a[i][j] == 2) {
                    a[i][j] = 0;
                    virus.add(new Pair(i,j));
                }
            }
        }
        recur(0,0);
        System.out.println(ans);
    }
}

[안드로이드] Splash screen 구현하는 방법

1.  Splash screen이란? 

먼저 안드로이드 앱에서 Splash screen이라고 하면 앱을 처음으로 실행시켰을 때 로딩 시에 나오는 화면을 뜻한다. 안드로이드 앱을 클릭하면 딜레이가 필연적으로 발생하는데 이 딜레이 시간 동안 사용자들에게 보여질 화면을 구현하는 것이다. 

가장 먼저 splash 화면에 사용될 이미지를 만들어준다. 보통 세로로 앱이 켜지니 세로 비율에 맞게 잘 이미지를 만들어주면 된다. 그리고 이러한 이미지를 drawable에 넣어준다.

---

 2. splash screen 구현방법

다음으로 splash 화면을 구현하기 위해서 drawable에 xml 을 하나 만들어준다. xml 파일에 앞서 만들어놓은 이미지를 배경으로 넣어주면 된다.

---

 

xml 파일이 만들어졌다면 이제 테마를 새로 만들어준다. Splash 화면을 위한 새로운 테마를 추가하는 것이다. styles.xml 에 들어가서 아래와 같은 코드를 추가해주면 테마를 만들 수 있다.

<resources>
//앞부분 코드
    <!-- For Splash Screen -->

    <style name="SplashTheme" parent="Theme.AppCompat.NoActionBar">    

        <item name="android:background">@drawable/splashfilename</item>   //앞에서 만들어놓은 drawable file 이름을 적으면 된다    

    </style>


</resources>

 

---

그 다음 화면이 처음 켜졌을 때 Splash Activity가 가장 먼저 실행되도록 순서를 바꾸어야 한다.

이는 AndroidManifest.xml에서 SplashActivity가 main 이 되도록 조정을 하면 된다.

 

<!-- AndroidManifest.xml -->
<application ...>
    <activity android:name=".SplashActivity"    android:screenOrientation="portrait"
        android:theme="@style/SplashTheme">
        <intent-filter>
            <action android:name="android.intent.action.MAIN" />
 
            <category android:name="android.intent.category.LAUNCHER" />
        </intent-filter>
    </activity>
</application>

이렇게 바꾸어주고 반면 원래 Main 으로 있었던 화면은 Main 부분을 지워주면 된다.

---

이제 마지막으로 SplashActivity에서 MainActivity로 넘어갈 수 있도록 SplashActivity.kt 을 만들어주고 코드를 작성해준다.

 

class SplashActivity : AppCompatActivity() {
    override fun onCreate(savedInstanceState: Bundle?) {

        super.onCreate(savedInstanceState)
        val intent = Intent(this, MainActivity::class.java) 
        startActivity(intent)

        finish()

    }

}

이렇게 작성해주면 처음 실행되는 SplashActivity에서 MainActivity로 넘어가게 되고 SplashActivity는 종료되게 된다. 따라서 finish () 이 부분도 꼭 작성해주어야 한다!