[강의]백준 알고리즘 2회차

지난 주 수업 추가분

Two Dots(16929, DFS/BFS, O(N*M))

• 사이클의 정의 (같은 색, 4개 이상 연결된 점들의 집합)
• 즉, 임의의 점에서 시작해서 길이가 4이상인 도착점(자기자신)이 있는지만 확인.
• DFS, BFS 모두 가능.

풀이1. 마지막 정점에서 find를 한 뒤 이미 방문했던 같은 색상의 점이 있다면 사이클이 존재. (일단 갔던 곳도 방문을 해 본 뒤, 뺄셈)

풀이2. 이전 칸과 다른 칸만 방문해서 이미 방문했던 곳으로 돌아오게 될 경우 사이클은 무조건 존재한다.

TIP: 다른 점에서 DFS를 다시 시작 할 경우 CHECK배열을 초기화할 필요가 없다.(사이클이 있었으면 이미 끝났고 다시 본다고 해도 사이클이 생기지도 않음).

모양만들기 (16932,DFS, BFS)

• N*M boolean배열에서 모양을 찾으려고 한다.
• 모양이란 연결되어 있는 1의 최대 개수 (그래프로 모델링 가능)
• https://www.acmicpc.net/problem/2667 비슷한 문제인데 조금 더 쉬운버전
• 이 문제는 조금 어렵다. (한 칸을 변경할 수 있기 때문에!)

[불가능]풀이1. 모든 0을 1로 변경하여 DFS/BFS를 모두 연산하는 방법 (시간이 오래 걸린다)

바꿀 수 있는 경우의 수 (NM) * O(NM) = O(N^2 M^2) - 불가능한 경우의 수

즉,

1. 완전 방법이 잘못되었거나
2. 불필요한 케이스를 줄여야한다.

위 경우는 2. 불필요한 케이스를 줄여야한다.에 해당

풀이2. BFS, DFS를 한 번 실행해서 모든 칸을 그룹짓고, 그룹의 크기를 미리 구해놓는다.

다음 모든 0을 1로 바꾸는 경우를 고려하여 BFS 없이 계산할 수 있다. (바꾸는 0을 기준으로 상하좌우를 조사하여 그룹이 연결되어있다면 값을 합친다.)

• c++의 unique를 사용했는데 뭐하는 놈인지 알아볼 것

나3곱2(16936, BFS 응용)

• 시작정수(x)를 (/3) 또는 (*2)를 반복하여 수열 A를 만든 뒤
• 숨바꼭질은 BFS로 풀 수 있는 기본 문제
• 숨바꼭질5와 비슷한 문제이다.
• 수학적지식(소인수분해)를 약간 이용한다.
• 3의 개수는 줄어들어야만하고 2의 개수는 늘어나야만 한다.

캠프준비(16938, 구현)

• 2<=N<=15, N=문제의 개수
• L<=난이도의합<=R, 최고난이도 - 최저난이도 >= X
• 최악의 경우의 수 = 2^N = O(2^N)
• 어려운 것: 최고난이도, 최저난이도 (무엇을 선택하는지에 따라 계속 변경됨)

풀이1과 2는 조삼모사

풀이1. 구현 후 필요한 조건만을 나열해서 전체 확인

풀이2. 선택과 동시에 모든 것을 처리함(재귀형태, 인자가 많다)

서울 지하철 2호선(16947, DFS/BFS 응용)

• N개의 정점과 N개의 간선으로 이루어진 그래프로 모델링가능!
• 트리(사이클이 없는 그래프, 정점N, 간선N-1)에서 간선을 하나 추가하면 사이클이 하나 생긴다.
• 모든 정점이 순환선(사이클)과 얼마나 떨어져 있는지를 알아야 한다.

따라서,

1. 사이클을 찾는다.
2. 사이클과의 거리를 구한다.

풀이. Two dot 문제와 비슷하게 사이클을 찾은 뒤 BFS 또는 DFS

까다로운 점: 사이클에 포함된 node를 모두 알아야 한다. (stack) 하지만, return 과정에서 사이클에 포함되지 않는 node도 stack에 들어있으므로 cycle의 시작점을 정확히 찾아야 한다. (필기참조)

• 거리를 구할 경우 BFS가 낫지만 이 경우 DFS가 낫다.

소스가 꽤 복잡하므로 필기자료를 참고할 것

    for (int y : a[x]) {
		//다음 이동할 점이 이전에 왔던 점이면 continue
        if (y == p) continue;
        int res = go(y, x);
        if (res == -2) return -2;
        if (res >= 0) {
			//check[x]=2인 것은 모두 순환선
            check[x] = 2;
            if (x == res) return -2;
            else return res;
        }
    }

A -> B (16953)

• 정수 A를 B로 최소 연산으로 바꾸려고 한다, (1<= A,B <=10^9)
  1. 2를 곱한다
  2. 1을 가장 오른쪽에 추가한다(*10 +1)

2^30 = 10억을 넘는다. 1을 오른쪽에 추가하는 것은 8번할 경우 10억을 넘는다.

풀이1 즉, 연산1은 30번, 연산2는 8번까지만 할 수 있다. 모든 경우를 다 시도해서 min값을 출력한다.

worst 경우의 수 = (30+8)!/(30!*8!) = 48903492

(Better)풀이2. 수학적지식 활용

문제를 반대로 푼다.(B->A)

1. 마지막자리가 짝수(0,2,4,6,8)인 경우는 무조건 /2
2. 마지막자리가 1인 경우는 무조건 연산2
3. 끝자리가 다른 수(3,5,7,9)는 만들 수 없다.

TIP: 문제의 제한은 꼭 지켜야하지만 문제의 조건은 반대로 생각하거나 무시해도 되는 경우가 있다. 예제문제: 보물

텔레포트(16958)

• 2차원 평면, N개의 도시(2<=N <=1000)
• (r1,c1) - (r2,c2) 이동시간 = |r1-r2| + |c1-c2| ( = 텔레포트 없이 이것보다 빠르게 갈 수는 없다.즉 최단거리를 구하기위해 BFS를 따로 쓸 필요는 없다.)
• 특별한 경우, 두 도시간의 이동시간가 T이다. (텔레포트)
• 두 도시의 쌍 M이 주어질 경우 최소 이동시간

문제는 텔레포트

• A에서 B로 가는 4가지 방법
  1. A -> B
  2. A -> A근처 특 -> B(B가 특별)
  3. A- > B근처 특 -> B(A가 특별)
  4. A -> A근처 특 -> B근처 특 -> B
• 텔레포트하는 시간은 T로 고정이므로 도착지에 가장 가까운 특별한 도시로 찾아가면 된다.

• 텔레포트는 무조건 0번이거나 1번이다… (모든 특별한 도시끼리는 텔레포트 가능!)

• A에서 B로 가는 2가지 방법 (텔레포트 0번 또는 텔레포트 1번)
  1. A -> B
  2. A -> A근처 특별한 도시(A포함) -> B근처 특별한 도시 -> B

(HARD)체스판 여행(16959, BFS)

• N*N 체스판이 있으며 1부터 N^2까지의 정수가 적혀있다.
• 1 -> 2 - > … -> N^2으로 이동하려 한다. (3<=N <=10)
• 중간에 다른 칸을 가도 된다. (1-5-6-2 가능)
• 같은 칸을 여러번 방문해도 된다. (BFS, DFS의 제약,,)
• 1에 나이트/비숍/룩 중 하나를 놓고 시작한다
• 1초 동안 할 수 있는 행동
  1. 말을 변경한다.
  2. 말을 이동한다.
• 필요한 시간의 최소값.

풀이1. DIVIDE AND CONQUER!

• (1->2), (2->3), … (N^2-1 -> N^2)으로 문제를 쪼갠다.
• 모든 최소를 합치면 답이 나올 것.
• 같은 칸을 여러번 방문할 경우 각 CASE의 최소가 절대 아니다. 따라서 무시해도 되는 조건이다.
• 따라서 가중치가 1인 그래프 AND 최소값을 구하는 것 = BFS
• 놓여져있는 말에 따라 노드에서 이동할 수 있는 방법이 달라지므로 말의 정보도 가지고 있어야 한다.
  1. 이동: (r, c, piece) -> (nr, nc, piece)
  2. 변경: (r, c, pirce) -> (r, c, piece[n])

위의 방법은 쪼갠 문제를 푸는 방법으로 모든 경우에 대해 적용한다.

풀이2. Divide and Conquer 이지만 한 번에 풀고싶다.

• 위와 같은 풀이이지만 BFS를 반복하고 싶지 않다.
• BFS의 인자에 num을 추가한다.

코드를 아주 조금만 변경하면 풀 수 있다고 합디다 ^^; 체스판여행2.. 비슷하지만 말을 바꾼 횟수(최소로 해서)를 출력해야 한다.

스위치와램프(16960, PASS)

(HARD)직사각형 탈출(16973, worth, 중복제거)

• NM 격자판에 HW 크기의 직사각형이 있다. (2<= N,M <=1000)
• 직사각형을 (Sr, Sc) -> (Fr, Fc)로 이동
• 이동방법 (상,하,좌,우)
• 벽이 존재(이동할 수 없음)

(불가능)풀이1. 모든 경우를 다 본다.

1. 11인 직사각형인 경우 O(NM) = 모든 정점을 방문
2. 크기가 HW이므로 4방향 중 하나를 검사하는데 걸리는 시간 O(HW)
3. 따라서 모든 칸을 방문 & 갈 수 있는지를 검사 = O(NMH*W) = 1,000,000,000,000 (1조) 불가능!

(불안전)풀이2. 중복을 줄인다.

1. 자기 자신에게 포함되는 칸들 = 벽이없다. = 조사하지 않는다.
2. 따라서 O(W) 또는 O(H)로 방향을 검사할 수 있다.
3. O(NMH + NMW)로 해결가능 = 20,000,000,000 (10억~20억)

약간 애매하지만 가능할수도?

풀이3. 중복을 또 줄인다.

1. 이미 검사한 칸은 모두 조사하지 않는다.

아 생각하기 싫다 ㅎㅎ prefix_sum(누적합).. 이라는게 있다고합니다

결론적으로 S[i][j] = (1,1) ~ (i,j)의 합이라고 처리하면 된다. S[i][j]=S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j]

[꼭]레벨 햄버거(16974, 재귀 시뮬레이션)

• 알고리즘이 어렵지는 않지만 코딩이 어려운 문제로 다음주에 몇 문제 더 풀 예정.
• 레벨-N 버거가 몇 장으로 이루어져 있는지 구한다. (1<=N<=50)

모든 것을 다 할 경우 2^50을 넘어갈 것. (불가능)

풀이1. 재귀 시뮬레이션

• 레벨-0 햄버거 = D[0] = 1
• 레벨-L 햄버거는 햄버거번, 레벨-L-1 버거, 패티, 레벨(L-1) 버거, 햄버거번
  • `D[L] = 1+ D[L-1] + D[L-1] +1 = 2D[L-1] + 3;
• go(n,x) = 레벨N 햄버거의 아래 X장을 먹었을 때, 먹은 패티의 수.

머리가 안굴러간다. 다시 읽어보자 ㅎㅎ,, Dp느낌으로 푸는 문제로 보여짐

다음 주 준비

준비하세오

(HARD)확장게임(16920)

BFS 스페셜 저지 (16940)

DFS 스페셜 저지 (16964)

체스판 위의 공(16957)