벽 부수고 이동하기 #2206

골드3

문제 이해

• N x M 크기의 그리드에 통과할 수 있는 공간 (0)과 통과할 수 없는 벽(1)이 주어진다
• (0,0)에서 (N-1, M-1)까지 이동하는 최단거리를 구한다
  • 단, 벽은 최대 하나까지 부수고 이동할 수 있다

해결 방안

1. Node 클래스 정의

큐에 추가될 Node 클래스를 정의한다. Node 클래스는 다음의 필드를 갖는다

• int y, int x
• int dist : 현재까지의 거리
• boolean brokeWall : 여태 1개의 벽을 부쉈는지 여부

2. 방문 여부 확인

우선 BFS의 기본인, 사방탐색을 통해 다음으로 방문하려는 노드가 이미 방문되었는지 여부를 체크해야 한다. 이를 위해 visited 배열을 관리할 것인데, 벽을 부수고 방문한 경우와, 벽을 부수지 않고 방문한 경우의 경로가 각각 다르기 때문에 구분해서 저장해야 한다.

int[][][] visited = new int[N][M][2];

// 벽을 한 번도 부수지 않고 온 경로로 현재 노드를 방문한다
visited[ny][nx][0] = 1; 

// 벽을 한 번 부수고 온 경로로 현재 노드를 방문한다.
visited[ny][nx][1] = 1; 

3. 그럼 언제 다음 노드를 방문하는가?

다음 노드를 방문하려면 꼭 필요한 공통 조건은 방문된 적 없는 노드여야 하는 것이다.

위에서 visited을 3차 배열로 구현한 것에서 알 수 있듯이, 노드 클래스의 brokeWall 변수를 활용해서 여태 벽을 부쉈는지 확인하고, 해당 상태(벽 부쉈는지 여부)에 대한 방문 여부를 확인해야 한다.

brokeWall==true, 즉 이미 벽을 부순 상태라면 visited[ny][nx][1]의 방문여부를 확인하고 업데이트해야 한다.

이 조건과 함께, 다음 세가지 조건 중 하나를 만족하는지 확인해야 한다.

이미 벽을 부쉈고, 다음으로 방문할 노드도 벽이면 최대 1개의 벽만 부술 수 있다는 문제의 조건을 만족할 수 없기 때문에 패스한다.

3-1. 이미 벽을 부쉈고, 다음 노드는 벽이 없을 때

• 벽을 이미 부쉈다 => current.brokeWall
• 다음 노드는 벽이 없다 => grid[ny][nx]==0
• 다음 노드를 현재 상태 (벽을 부순 상태)로 방문한 적이 없다 => visited[ny][nx][1]==0

if (current.brokeWall && grid[ny][nx] == 0 && visited[ny][nx][1] == 0) {
     queue.add(new Node(ny, nx, current.dist + 1, true));
     visited[ny][nx][1] = 1;
} 

3-2. 벽을 부수지 않았고, 다음 노드도 벽이 없을 때

• 벽을 부수지 않았다 => !current.brokeWall
• 다음 노드는 벽이 없다 => grid[ny][nx]==0
• 다음 노드를 현재 상태 (벽을 부수지 않은 상태)로 방문한 적이 없다 => visited[ny][nx][0]==0

if (!current.brokeWall && grid[ny][nx] == 0 && visited[ny][nx][0] == 0) {
      queue.add(new Node(ny, nx, current.dist + 1, false));
      visited[ny][nx][0] = 1;
}

3-3. 벽을 부수지 않았고, 다음 노드가 벽일 때

• 벽을 부수지 않았다 => !current.brokeWall
• 다음 노드는 벽이다 => grid[ny][nx]==1
• 다음 노드를 현재 상태 (벽을 부수지 않은 상태)로 방문한 적이 없다 => visited[ny][nx][1]==0

if (!current.brokeWall && grid[ny][nx] == 1 && visited[ny][nx][1] == 0) {
    queue.add(new Node(ny, nx, current.dist + 1, true));
    visited[ny][nx][1] = 1;
}

코드 설명

벽 부수고 이동하기 백준 #2206 풀이 코드

삽질

이번 삽질의 가장 치명적인 점은 distance를 배열로 관리하겠다는 틀에 박힌 사고였다. 방문여부와 distance를 하나의 배열로 관리하는 코드의 단점을 뼈저리게 느꼈다.

방문했는지,

보완점

이번에는 ny, nx 인덱스 값이 그리드의 인덱스 범위를 벗어나면 continue하도록 구조를 바꿔봤다.

원래는 범위 값 내면 코드를 수행하는 방식으로 코드를 짰었는데, 요 방법이 코드의 가독성에 더 도움이 되는 것 같다.

---

하노이 탑에 대하여

[Gold V] 하노이 탑 이동 순서 #11729
[Gold V] 하노이 탑 #1914

개념 이해

하노이 탑은 대표적인 재귀 알고리즘 문제인데, 오늘 첫 만남을 치뤘다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다
2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다

위의 두가지 조건을 만족하면서 첫 탑에 있는 n개의 원판들을 모두 세번째 탑으로 옮겨야 한다. 두번째 탑은 보조 탑으로 사용하면 된다.

하노이탑의 이동을 제대로 이해해보자

아직 원판이 2개 이상 있는 경우에는 원판을 다회 이동해야 한다.

3개의 원판으로 예시를 들어보자

  -
 ---
-----
  A      B      C

시작에는 A 위치에 원판 3개 모두 비치되어있고, 우리의 목표는 목적지인 C에 3개의 원판을 모두 이동시키는 것이다.

길이 1의 원판을 1번 원판, 길이 3의 원판을 2번 원판, 길이 5의 원판을 3번 원판이라 가정하자.

3번 원판부터 차례로 C에 도달해야 되기 때문에 1번과 2번 원판은 B에 위치해야 한다는 것을 알 수 있다. 2번 원판이 B에 있어야 1번 원판을 그 위에 쌓을 수 있기 때문에 1번 원판을 이동하는 시점에는 B가 비어있어야 한다. 그래서 우리는 1번 원탑을 C로 이동시킨다.

 ---
-----           -
  A      B      C

그 다음 2번 원탑을 움직일 수 있으니 B로 이동시킨다.

-----   ---     -
  A      B      C

이제 3번 원판을 C로 이동시켜야 하니 C에 있는 1번 원판을 B로 이동 시키자. B에 있는 2번 원판보다 1번 원판의 길이가 더 짧으니 2번 위에 올릴 수 있다.

	     -
-----   ---
  A      B      C

이제 A에 있는 3번 원판을 움직일 수 있다. C로 이동 시키자.

	     -
        ---   -----
  A      B      C

B에 있는 1번과 2번 원판도 C로 옮겨주려면 2번 원판부터 3번 원판 위로 옮겨줘야 한다. 그러기 위해서는 1번 원판을 A로 옮긴 다음, 2번 원판을 C로 이동시키자.

                                             ---
  -     ---   -----     ->      -           -----
  A      B      C               A      B      C

마지막으로 A의 1번 원판을 C로 이동시켜서 하노이 원탑을 완성시킨다.

                -
               ---
              -----
  A      B      C

여태까지의 과정을 "X" 위치의 가장 위 원판을 "Y" 위치로 이동한다는 의미에서 "X Y"로 표현해보면 다음과 같다

A C
A B
C B
A C
B A
B C
A C

A를 1, B를 2, C를 3으로 바꿔서 보면 #1914에서 예시 입출력과 같음을 확인할 수 있다.

해결방안 고안

1. 재귀 base case

재귀를 탈출하는 베이스 케이스의 조건은 원판의 수가 1개일 때다. 이 때는 현재 원판의 위치에서 도착지의 위치로 이동하면 끝이다.

즉, start을 현재 위치라 가정하고, dest가 목적지면 이 경우의 경로는 start 탑의 원판을 dest 탑으로 옮기는 것이다.

2. 재귀 반복

결국 원탑을 시작점에서 목적지로 이동하기 위해서는 다음을 수행한다.

1. N-1개의 원판을 중간지점으로 옮긴다.
2. 가장 큰 원판을 목적지로 옮긴다.
3. N-1개의 원판을 목적지로 옮긴다.

코드로 짜보면 다음과 같다.

static void hanoi(int numPlates, int start, int by, int dest) {
	if (N == 1) { // 베이스케이스
    	sb.append(start).append(" ").append(dest).append("\n");
        return;
    } else {
    	hanoi(numPlates - 1, start, dest, by);
        sb.append(start).append(" ").append(dest).append(NEW_LINE);
        hanoi(numPlates - 1, by, start, dest);
    }
}

총 이동횟수 계산

사실 하노이 탑 문제 중에서는 그냥 재귀함수 안에서 베이스케이스 호출 횟수에 대해 카운터를 증가시켜 총 이동횟수를 게산할 수 있는 문제들도 있다.
하지만 하노이탑 #1914 와 같은 경우에는 N 입력값이 20 초과면 재귀 함수를 호출하는 것이 아닌 이동 횟수만 출력하면 되기 때문에 계산을 해야 한다. 특히 그 정도로 큰 입력값이면 재귀가 미친듯이 깊어질 것이다.

#1914에서 이동 횟수 출력 이슈

백준 #1914에서 N의 최대 입력값은 100이기 때문에 3번에서 확인한 총 이동횟수 계산식을 따르면 2^100-1으로 long 타입의 범위를 벗어나게 된다.

그래서 long보다 큰 범위를 허용하는 java.math.BigInteger를 활용해야 한다.

[JAVA] long보다 큰 숫자 BigInteger

간단한 제곱 연산 메서드를 통해 구하면 된다.

private static BigInteger solve(int N) {
	BigInteger two = new BigInteger("2");
    return two.pow(N).subtract(new BigInteger("1"));
}

---

오큰수 #17298

골드4

문제 이해

숫자 배열이 주어진다.
나의 오른쪽에 있는 수 중 나보다 큰 가장 왼쪽의 수를 찾는 것.

nums[i]의 오큰수인 nums[j]는 다음 조건을 만족한다

• i < j
• nums[i] < nums[j]
• 위 조건을 만족하는 최소 j 값

해결 방안 고안

배열을 스택에 담아 풀이하고자 한다.

스택에는 아직 오큰수를 만나지 못한 숫자들의 인덱스를 담고, 배열의 인덱스를 1부터 순차적으로 비교한다.

만약 스택의 머리 값보다 큰 값을 배열에서 만나면, 이는 스택의 모든 요소보다 크다는 것을 의미하기 때문에 stack의 모든 인덱스에 이 배열 값을 오큰수로 저장하면 된다.

예제를 통해 이해해보자.

arr = {3, 5, 2, 7};

스택은 첫 인덱스 0을 담고 시작한다.

1. 첫 루프

스택의 머리는 3이다.
배열을 5부터 순회하는데, 5가 3보다 크고, 가장 인덱스가 작은 값이기에 3의 오큰수는 5다.

그 다음 5를 스택에 추가한다

2. 두번째 루프

스택의 머리는 5다.
배열을 2부터 순회한다.

2-1. 2는 5보다 작아서 오큰수가 되지는 못한다.
스택에 추가한다.

2-2. 그 다음 7은 5보다 커서 오큰수다.
이 말은 곧 즉슨, 7이 2의 오큰수라는 뜻이다.
그래서 스택이 빌 때까지 pop하면서 오큰수에 저장한다.

코드

오큰수 #17298

---

요세푸스 문제

실버#4

문제 이해

• N명의 사람이 1번부터 N번까지 순서대로 원을 이뤄 앉아있음
• 양수 K가 주어지면, 순서대로 K번째 사람을 제거한다
• 원에서 사람들이 제거되는 순서를 출력한다

해결 방안 고안

• 순서가 있는 데이터의 집합이라 ArrayDeque과 같은 자료구조를 잘 활용할 수 있는 문제다
• 하!지!만! 링크드리스트 구현한지가 오래되어 나는 링크드리스트로 구현해보았다 (저번주에 배운listIterator에서 영감을 받음)

풀이 코드

1. Node 클래스

사람의 번호를 저장할 data 필드, 내 왼쪽에 앉아있는 사람(Node)에 대한 포인터인 prev 필드, 그리고 내 오른쪽 사람에 대한 포인터인 next 필드가 존재한다.

메서드는 생성자만 필요하다.

2. CircularLinkedList

링크드리스트의 첫 노드를 저장할 Node head, 마지막 노드를 저장할 Node tail, 링크드리스트의 크기를 저장할 int size, 그리고 어느 노드를 제거할지 트랙킹할 Node cursor 필드를 갖는다.

메서드는 다음과 같이 필요하다

• 생성자: 링크드리스트의 크기를 0으로 초기화한다
• boolean isEmpty(): 링크드리스트의 크기가 0인지 불리언 값으로 반환한다
• void add(Node newNode): 첫 노드 추가, 두번째 노드 추가, 이외 노드 추가를 구분하여 구현했다. 사이즈 크기를 1 증가시킨다
• int next(): cursor를 오른쪽으로 한칸 움직인다. listIterator의 메서드를 모방했다
• int remove(): 현재 커서에 해당하는 노드를 제거한다. 커서 노드가 머리 또는 꼬리였다면 reassign 작업도 진행한다

3. 전반적인 로직 구성

입력된 N에 대하여 1~N까지 원형 링크드리스트에 추가한다. 원혀 링크드리스트가 모두 소모될 때까지 K번째 노드를 찾아 (next()) 제거(remove())하고, 이 제거된 데이터 값을 순열에 저장한다.

마지막으로 순열을 출력한다.

요세푸스 문제 #1158 풀이코드

---

풍선 터뜨리기

실버#3

문제 이해

• 1번부터 N번까지 N개의 풍선이 원형으로 번호순대로 놓여져있다.
• 첫 시도에는 무조건 1번 풍선을 터뜨린다.
• 터뜨린 풍선의 데이터값 K를 받아 K번째 풍선을 터뜨린다
  • 모든 풍선을 터뜨릴 때까지 이 작업을 반복한다
  • K는 음수거나 양수다.

해결 방안 고안

• <요세푸스> 문제에서 구현한 링크드리스트를 최대한 활용해보았다
• 커서가 왼쪽(음수)이나 오른쪽(양수)으로 이동할 수 있기 때문에 next() 메서드 대신에 move() 메서드를 구현하여 왼쪽과 오른쪽 이동을 모두 구현했다.

풀이 코드

<요세푸스 문제>의 Node와 CircularLinkedList 클래스를 그대로 사용했다.

void move(int times) 메서드

이동 횟수를 인자값으로 받아서 커서를 이동시킨다. 인자값이 음수면 현재 커서의 .prev 노드로 이동하고, 양수면 현재 커서의 .next 노드로 이동한다.

풍선 터뜨리기 #2346 풀이 코드