[백준]1913번 달팽이

1913번: 달팽이

2022.09.08 달팽이 문제 다시 풀어보기

너무 “완전한 규칙 찾기에 얽메이지 않으려고" 노력했다.

이제까지 그렇게 하려다 보니 혼자 혼란에 빠져서 못 푼 경우가 많았기 때문이다.

이번에는 이렇게 했다.

• (n/2,n/2) 에서 시작한다
• n = 3 인 경우 이동을 보면
  • ⬆️➡️ , ⬇️⬇️ ⬅️⬅️, ⬆️⬆️ 에서 끝이 나고
• n = 5 인 경우 이동을 보면
  • ⬆️➡️ , ⬇️⬇️ ⬅️⬅️, ⬆️⬆️⬆️ ➡️➡️➡️, ⬇️⬇️⬇️⬇️ ⬅️⬅️⬅️⬅️, ⬆️⬆️⬆️⬆️ 에서 끝이 난다.
• Up + LEFT 로 가는 이동과 DOWN + RIGHT 로 가는 이동을 각각 묶어준다.
• 각 이동을 별개의 함수로 두고, 함수 에서는, repeat 수만큼 UP 을 하고 repeat 수 만큼 LEFT 로 이동한다.
  • 이 때 UP 을 하는 과정에서 (0,0) 에 도달하면 멈춘다.

package learningJava.algorithm.pang;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    private BufferedReader br =
        new BufferedReader(new InputStreamReader(System.in));
    private BufferedWriter bw =
        new BufferedWriter(new OutputStreamWriter(System.out));
    private int target;
    private int n;
    private int[][] board;
    private int cnt;
    private void input() throws Exception {
        n = Integer.parseInt(br.readLine());
        target = Integer.parseInt(br.readLine());
        board = new int[n][n];
        cnt = 1;
    }

    private void solve() throws IOException {
        int c = n/2; // center
        int cr = c; int cc = c; // 시작점인 r, c
        int ar = 0; int ac = 0; // 정답 좌표
        int repeat = 1;
        int[] current = new int[]{cr,cc};

        board[cr][cc] = cnt++; // 시작점을 세팅한다 

        while((current = upAndRight(repeat++, current[0], current[1])) != null) {
            current = downAndLeft(repeat++, current[0], current[1]);
        }

        for(int i = 0 ; i < n; i++ ){
            for(int j = 0; j < n; j++) {
                if(board[i][j] == target) {
                    ar = i + 1;
                    ac = j + 1;
                }
                bw.write(board[i][j] +" ");
            }
            bw.write("\n");
        }
        bw.write(ar+" "+ac);
        bw.flush();
    }

    // 여기서는 (0,0) 에 도달하는지를 확인해야한다  - repeat 횟수만큼 이동한다
    // 마지막 이동 위치를 리턴한다
    private int[] upAndRight(int repeat, int cr, int cc) {
        int[][] dirs = new int[][]{{-1,0},{0,1}}; // 위로, 오른쪽
        int r = cr;
        int c = cc;

        for(int[] dir : dirs) {
            for(int n = 0 ; n < repeat ; n++) {
                r += dir[0];
                c += dir[1];

                board[r][c] = cnt++;

                if(r == 0 && c == 0) return null;
            }
        }

        return new int[]{r,c};
    }

    private int[] downAndLeft(int repeat, int cr, int cc) {
        int[][] dirs = new int[][]{{1,0},{0,-1}}; // 아래로, 왼쪽으로

        int r = cr;
        int c = cc;

        for(int[] dir : dirs) {
            for(int n = 0 ; n < repeat ; n++) {
                r += dir[0];
                c += dir[1];

                board[r][c] = cnt++;
            }
        }

        return new int[]{r,c};
    }

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.input();
        main.solve();

    }
}

문제 풀이

(1:30)

작년 하반기 부터 보던 코테에서 이런 문제가 굉장히 많이 나오고 있고 나는 매 번 풀 지 못하고 있다.

레벨은 낮은 문제임에도 마냥 어렵게 느껴졌다.

import java.io.*;
import java.util.*;

public class Main {

  public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  public static int parseInt(String target){ return Integer.parseInt(target);}
  public static StringTokenizer st;
  public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static int target;
  public static int tr, tc; // target 위치
  public static int n;
  public static int[][] board;
  public static int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}}; // 오른쪽, 왼쪽, 아래, 위

  public static void setting() throws IOException {
    n = Integer.parseInt(br.readLine());
    board = new int[n][n];
    target = Integer.parseInt(br.readLine());
  }
  public static void fill(){
    int circle = n/2; // 바퀴 수
    // 현재 위치
    int[] loc = new int[2];
    loc[0] = circle;
    loc[1] = circle;
    board[loc[0]][loc[1]] = 1;

    int movNumb = 1;
    // 이동 횟수
    // n 은 항상 홀수이기 때문에 (위, 오른쪽, 아래, 왼쪽, 위 ) 의 패턴을 계속한다
    int cnt = 2;
    int circleCnt = 0;

    while (circleCnt < circle){
      // 맨 처음에는 위로 한 칸 이동 하는 거로 시작
      cnt = move(loc, 3, 1, cnt);
      // 오른쪽 이동
      cnt = move(loc, 0, movNumb, cnt);
      // 아래로 이동
      movNumb++;
      cnt = move(loc, 2, movNumb, cnt);

      // 왼쪽 이동
      cnt = move(loc, 1, movNumb, cnt);

      // 마지막에 위로 이동
      cnt = move(loc, 3, movNumb, cnt);
      movNumb++;
      circleCnt++;
    }

    // target 이 1 인 경우는 따로 업데이트 ( 시작 cnt 를 2로 했어서 )
    if (target == 1) {
      tr = circle; tc = circle;
    }

  }
  // 정답 출력 메소드 
  public static void printBoard() throws IOException{
    for(int r = 0 ; r<n;r++){
      for(int c =0;c<n;c++)
        bw.write(board[r][c]+" ");
      bw.write("\n");
    }
    bw.write((tr+1)+" "+(tc+1)+"\n");
    bw.flush();
    bw.close();
  }
  // 현재위치, 방향, 이동횟수
  public static int move(int[] loc, int dir, int movCnt, int cnt){
    for(int cur = 0 ; cur < movCnt; cur++){
      loc[0] += dirs[dir][0];
      loc[1] += dirs[dir][1];
      board[loc[0]][loc[1]] = cnt++; // board 에 값을 채워 넣는다
      // target 칸 인 경우
      if( board[loc[0]][loc[1]] == target){
        tr = loc[0];
        tc = loc[1];
      }
    }
    return cnt;
  }
  
  public static void main(String[] args)throws IOException {
    setting();
    fill();
    printBoard();
  }
}