[19주차_월요일] 통나무 옮기기

[icegosimperson]

• 사이트 : 백준(BOJ)
• 문제: 통나무 옮기기
• 번호: 1938
• 레벨: 골드2

### 🤔 시간복잡도 고려사항



### 💡 풀이 아이디어

[yeongleej]

🤔 시간복잡도 고려사항

• 평지 한 변의 길이: N <= 50

=> BFS 탐색 : O(N * N) 가능

💡 풀이 아이디어

• BFS 탐색

  • 통나무의 중심점의 방문 체크 진행
  • (i, j) 지점에서 통나무가 가로일 수도, 세로일 수도 있으므로 3차원 방문배열 생성
  • 0(세로): visited[i][j][0] => 통나무의 중심점이 (i,j)에서 세로로 방문함
  • 1(가로): visited[i][j][1] => 통나무의 중심점이 (i,j)에서 가로로 방문함

• 중심점 이외의 나머지 통나무들 위치 찾기

  • BFS 탐색 시, 탐색 저장 객체를 Step으로 지정

  static class Step {
  	int x, y;	// 통나무의 중심점
  	int dir;	// 세로: 0, 가로: 1
  	int cnt;	// 이동한 칸수
  	public Step(int x, int y, int dir, int cnt) {
  		super();
  		this.x = x;
  		this.y = y;
  		this.dir = dir;
  		this.cnt = cnt;
  	}
  }

  • 현재 통나무의 중심점 (now.x, now.y)을 바탕으로, dir을 통해 세로 통나무인지, 가로 통나무인지 파악해서 나머지 통나무들 구함

             // 방향벡터 : 상, 좌, 하, 우
  	int ax = now.x + dx[nDir];
  	int ay = now.y + dy[nDir];
  	int bx = now.x + dx[nDir+2];
  	int by = now.y + dy[nDir+2];

• ** canTurn() : 통나무 회전 시, 통나무를 둘러싸고 있는 3*3 정사각형 안에 다른 나무가 없는지 체크하기

  public static boolean canTurn(int x, int y) {
  	for(int i=x-1; i<x+2; i++) {
  		for(int j=y-1; j<y+2; j++) {
  			if(!inRange(i, j)) return false;
  			if(g[i][j] == '1') return false;
  		}
  	}
  	return true;
  }

처음에 회전하는 방향에만 1이 없다면 통나무를 회전시킬 수 있을 거라고 생각했는데, 3 * 3 크기안에 1개의 나무라도 있으면 안되는 것 같습니다,,,,, ㅎㅎㅎ

[baexxbin]

🤔 시간복잡도 고려사항

• 4 ≤ N ≤ 50
• 완전탐색 N^2
• BFS N^2

완전탐색도 O(N^2)이 맞나요..? 완탐이 더 오래걸릴거같은데 왜 똑같은거죠..? 잘못생각한건가요..

💡 풀이 아이디어

• BFS 이용
  • 처음엔 완전탐색을 생각했으나, 시작지점B에서 목표지점E로 간다는 점이 bfs의 개념과 일치
  • 우선 날개는 생각하지 않고 중심좌표를 기준으로 bfs진행
    • 가로, 세로 두가지의 타입이 있기에 3차원 배열 이용
    • valid검사 시 양옆의 날개 고려하기
• 입력 받기 및 전처리
  • B,E 알파벳 자리는 0으로 치환해서 board배열 구성
  • 각 시작 B, E의 중심점을 찾기위해 리스트로 입력받은 후 정렬 진행
    • 가운데(1)번에 해당하는 점이 중심좌표
    • 가로 (0) / 세로 (1)
• BFS
  • 중심좌표 기준 3차원 bfs진행
  • 타겟좌표와 타입이 같으면 도착: 방문길이 반환
  • 각 동작에 대한 valid 작성
    1. 중심좌표 유효한지 확인
    2. 가로, 세로 각 경우의 양날개 유효한지 확인
    3. 회전할때 3*3 부분이 다 유효한지 확인

private static boolean canWingRow(int r, int c) {       // 가로일때 날개 유효한지
  return isValid(r, c-1) && isValid(r, c+1) && board[r][c - 1] == 0 && board[r][c + 1] == 0;
}

private static boolean canWingCol(int r, int c) {       // 세로일때 날개 유효한지
  return isValid(r-1, c) && isValid(r+1, c) && board[r-1][c] == 0 && board[r+1][c] == 0;
}

private static boolean canTurn(int r, int c, int t) {
  for (int i = r - 1; i <= r + 1; i++) {
      for (int j = c - 1; j <= c + 1; j++) {
          if (!isValid(i, j) || board[i][j]==1) return false;
      }
  }
  return true;
}

• 주의해야할 점
  • 타입(가로, 세로) 계산을 위해 (^) XOR연산 사용
    • 처음에 더 깔끔한 ~ (NOT)를 사용했는데 이건 모든 비트를 반전시키는 연산임
    • 최종적으로는 2의 보수가 됨..
  • 회전가능한 3*3검사
    • 처음엔 복잡하게 현재 해당하는 부분빼고 for문을 구성했는데,, 그럼 복잡해짐
    • 이런건 깔끔하게 싹 검사하기

[KodaHye]

🤔 시간복잡도 고려사항

• 4 ≤ N ≤ 50
• BFS를 통한 탐색
  • 2 × 50 × 50 × 4
  • 50 × 50 크기의 맵에서 기준점이 있을 때 수평/수직 두 가지 상태로 있을 수 있으며, 상, 하, 좌, 우로 움직일 수 있음
• 중복조합을 통한 완전탐색
  • 상/하/좌/우/회전을 할 수 있고, 나무의 중심점이 위치할 수 있는 공간이 최대 250개이므로 방문처리를 하면 더 적어지겠지만, 5 ^ 250 정도 될 것이라고 생각 (시간 초과)
  • 5 ^ 12만 해도 2억이 넘기 때문에 상/하/좌/우/회전에 대해 중복조합하면 안됨

💡 풀이 아이디어

길이가 3인 통나무의 중심점과 통나무가 수평/수직 중 어떻게 있는지 확인하면서 BFS 진행하기

변수명	설명
final boolean VERTICAL	통나무가 세로로 길게 위치하고 있으면 VERTICAL == true
Tree.class	나무의 정보 저장 (중심점의 좌표: r, c, 세로 모양으로 있는지 여부: isVertical)
Node.class	통나무의 중심을 기준으로 bfs를 할 때, 단계(depth)를 저장해여되므로 Tree t와 int depth를 변수로 갖음
Tree start, end	통나무 시작점과 끝점

• findTree(char[][] map)

  • 통나무의 시작점과 끝점 찾기
  • 시작점: BBB로 구성될 때, 가운데 지점 좌표와 통나무가 어떤 방향(수평/수직)으로 위치하고 있는지 저장
  • 끝점: EEE로 구성될 때, 가운데 지점의 좌표와 통나무가 어떤 방향(수평/수직)으로 위치하고 있는지 저장

• bfs()

  • 시작점을 기준으로 bfs 시작하기
  • 통나무의 위치가 한 좌표에서 수평/수직 두 가지 경우로 존재할 수 있기 때문에 3차원 방문 배열 사용
  • 시작 지점의 좌표, 수평/수직 상태와 끝 지점의 좌표, 수평/수직 상태가 같다면 bfs 끝내기
  • bfs를 진행할 때, 통나무 3개가 동시에 위치할 수 있는지(canPositTree) 확인해야 됨
  • bfs를 진행하기 위해 다음 지점을 갈 때는 통나무의 기준점을 상/하/좌/우로 옮기거나, 기준점은 그대로 한 채 수평/수직의 상태를 반대로 해줘야 됨
    • 수평/수직의 상태는 3차원 배열로 확인함
    • 수직상태(VERTICAL_IDX): 0, 수평상태(HORIZONTAL_IDX): 1
    • 비트 연산을 통해 0일 때는 1, 1일 때는 0으로 바뀔 수 있도록 함: 1 ^ currentIdx

• boolean canPositTree(int r, int c, boolean isVertical)

  • 통나무의 기준 좌표가 r, c이고 수평/수직 상태가 isVertical일 때 양 옆에 위치해야 될 통나무들이 좌표를 벗어나는지와 다른 나무가 이미 있어서 위치할 수 없는지 확인

• boolean canRotate(int r, int c)

  • 해당 지점에서 회전할 수 있는지 확인
  • 통나무의 기준점을 기준으로 3 × 3 구간을 확인해줘야 됨

틀린게 없는데 계속 틀려서 일단 의심 가는거 조금씩 바꾸면서 계속 제출했었는데, 회전 부분에서 3 × 3 구간을 모두 확인한게 아니라 움직일 부분만 확인해줬네요!!
문제 똑바로 읽겠습니다아악!!!!!!

[Jewan1120]

🤔 시간복잡도 고려사항

• 4 ≤ N ≤ 50
• 움직임 4개, 회전 1개
• 50 x 50 x 5 x 2 = 25,000 → 완전 탐색 가능

💡 풀이 아이디어

• 통나무를 BFS로 움직이면서 최소 동작 횟수 반환
• 처음 위치(BBB)와 최종 위치(EEE)의 위치를 저장해주고, 위치에 따라서 상태를 기록 → 가로: 0, 세로: 1

  int[][] bArr = new int[3][2]; // 처음 위치
  int[][] eArr = new int[3][2]; // 최종 위치
  // ~~
  int sy = bArr[1][0], sx = bArr[1][1], st = bArr[0][0] == bArr[1][0] ? 0 : 1; // 처음 위치의 중심점 및 상태
  int ey = eArr[1][0], ex = eArr[1][1], et = eArr[0][0] == eArr[1][0] ? 0 : 1; // 최종 위치의 중심점 및 상태
  ``

• 방문 처리를 현재 상태도 포함하여 관리될 수 있도록, int[][][]로 하여, 최단 시간을 기록
• BFS 진행 순서는 이동 → 회전 순으로 구현
• BFS를 진행할 때, 통나무 전체가 움직이는 것이 아닌 중심 좌표만 이동하게 하여, 간단하게 이동 진행 → 이동 가능지 체크할 때, 추가적인 연산은 필요

  // 통나무 전체가 이동할 수 있는지 확인
  private static boolean isValid(int y, int x, int t) {
      // 가로 방향
      if (t == 0) {
          if (isValid(y, x - 1) && isValid(y, x) && isValid(y, x + 1)) // 유효한 범위이며
              if (!board[y][x - 1] && !board[y][x] && !board[y][x + 1]) // 이동하는 방향에 나무가 없어야 함
                  return true;
      // 세로 방향
      } else {
          if (isValid(y - 1, x) && isValid(y, x) && isValid(y + 1, x))
              if (!board[y - 1][x] && !board[y][x] && !board[y + 1][x])
                  return true;
      }
      return false;
  }
  
  // 경계 체크
  private static boolean isValid(int y, int x) {
      return 0 <= y && y < n && 0 <= x && x < n;
  }

• 회전에 대해서는 중심점을 둘러싼 3x3에 나무가 있는지 없는지만 체크

  private static boolean canRotate(int y, int x) {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            int ny = y - 1 + i, nx = x - 1 + j;
            if (!isValid(ny, nx) || board[ny][nx])
                return false;
        }
    return true;
  }

[icegosimperson]

🤔 시간복잡도 고려사항

N<=50, 50* 50, 4 * (2) : BFS 탐색 가능

💡 풀이 아이디어

• findPosition() : 시작 위치와 방향 계산
• Node(int x, int y, int dir, int cnt) : 좌표, 방향, 이동 횟수 저장 객체
• Bfs() : 현재 Node가 목표 상태와 일치하는지 확인 -> cnt++
  • 상하좌우 이동 가능한지(isValid, check) 확인 -> 방문처리 -> 큐에 추가
  • 회전 가능 여부 확인(canRotate) -> 방문처리 -> 큐에 추가
  • visited[x][y][dir] : 방향까지 확인해야되기 때문에 3차원
• boolean isValid() : 격자 범위 안에 있는지, 장애물이 있는지 확인
• boolean check() : 가로 방향, 세로 방향일 경우 나눠서 3x3 범위에 장애물이 있는지 확인

    private static boolean check(int nx, int ny, int dir) {
        if (!isValid(nx, ny)) return false;
        if (dir == 0) {
            return isValid(nx, ny - 1) && isValid(nx, ny) && isValid(nx, ny + 1);
        } else {
            return isValid(nx - 1, ny) && isValid(nx, ny) && isValid(nx + 1, ny);
        }
    }

• boolean canRotate() : 통나무(BBB)가 현재 위치에서 회전할 수 있는지 확인

private static boolean canRotate(int x, int y) {
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                int nx = x + i, ny = y + j;
                if (!isValid(nx, ny)) {
                    return false;
                }
            }
        }
        return true;
    }

⭐ 참고한 것

• 통나무 시작 위치와 방향 계산, 통나무 방향 전환
• 처음 작성한 코드

        for(int i=0; i<n; i++) {
            String input = br.readLine();
            for (int j = 0; j < n; j++) {
                board[i][j] = input.charAt(j);
                if (board[i][j] == 'B') {
                    startX = i;
                    startY = j; // 중심 좌표 기준으로 관리하기 위한 좌표 저장
                } else if(board[i][j]=='E'){
                    targetX = i;
                    targetY = j; // 도착 좌표
                }
            }
        }
        startDir = (0<startY && board[startX][startY-1]=='B') ? 0:1;
        targetDir = (0<targetY && board[targetX][targetY-1]=='E') ? 0:1;

• 문제점 : 처음 발견된 시작점(B)와 목표지점(E) 좌표 기준으로 설정했기에, BFS 탐색 시 이동(상하좌우) or 회전이 잘못될 수 있음

• 참고하여 개선한 방법

  • 중심 좌표(centerX, centerY)를 계산(/3)하여 목표 좌표를 설정

   private static int[] findPosition(char target) {
       int sumX = 0, sumY = 0, dir = 0;

       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
               if (board[i][j] == target) {
                   sumX += i;
                   sumY += j;
               }
           }
       }
       int centerX = sumX / 3; // 중심 좌표 계산 /3
       int centerY = sumY / 3; // 

       if (0 < centerY && board[centerX][centerY - 1] == target) {
           dir = 0; // 가로
       } else {
           dir = 1; // 세로
       }
       return new int[]{centerX, centerY, dir};
   }

• 통나무 방향 전환 : nextDir = 1-dir
  • dir : 0 (가로), 1(세로)
  • 가로일 때, 1-0 = 1 (세로 전환)
  • 세로일 때, 1-1 - 0 (가로 전환)