[백준]JAVA - 1913번: 달팽이

https://www.acmicpc.net/problem/1913

1913번: 달팽이

풀이

실버3 난이도의 구현 문제로 생각보다 오래 걸렸다...

 

문제를 시작하기에 앞서 시작 위치와 방향 전환에 대해서 고민해봐야 한다.

우선 왼쪽 그림처럼 (0, 0) 을 시작점으로 두고 시작하게 되면 숫자가 1씩 작아지고, 오른쪽 그림처럼 (N/2, N/2) 에서 시작하게 되면 숫자가 1씩 증가한다. 또한 나아가는 방향의 순서도 반시계 방향, 시계 방향으로 달라진다.

 

공통적으로 방향 전환에 대해서 고민해봐야 할 필요가 있다.

 

int형 배열로 선언하게 되면 모든 값이 0으로 들어간다. 그렇다면 0이 아닌 값은 이미 방문했다는 소리다.

한 방향으로 진행하다가 배열의 범위를 넘어갔거나 0이 아닌 값을 만났을 경우 방향 전환을 해주면 된다.

 

마지막으로 4 방향을 다 돌았을 경우에 다시 0으로 초기화해주고 돌아가면 된다.

// 하, 우, 상, 좌를 다 반복했을 경우 처음부터 시작
if (idx == 4) {
    idx = 0;
}

필자가 선택한 건 왼쪽 그림이다.

이유는 오른쪽 그림보다 간단하다고 생각했고 실제로도 그랬다.

 

필자는 주로 BufferedReader 와 System.out.println() 쓴다. 이 또한 이유는 없다. 그냥 익숙해서(?)..

위 문제를 풀면서 시간초과가 발생해서 System.out.println() 만 BufferedWriter 로 바꿔서 제출했더니 통과했다.

이번 계기로 속도 차이를 실감할 수 있었고, 앞으로 풀 알고리즘은 BufferedReader 와 BufferedWriter 를 이용해서 풀 예정이다.

 

<최종코드>

import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        int num = N * N;
        int[][] map = new int[N][N];
        
        int x = 0;
        int y = 0;
        int idx = 0;
        
        while(true) {
            map[x][y] = num;
            
            int nx = x + dx[idx];
            int ny = y + dy[idx];
            
            // 범위에서 벗어나거나 값이 이미 들어있을 경우 방향 전환
            if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] != 0) {
                idx++;
            }
            
            // 하, 우, 상, 좌를 다 반복했을 경우 처음부터 시작
            if (idx == 4) {
                idx = 0;
            }
            
            x += dx[idx];
            y += dy[idx];
            num--;
            
            if (num == 0) break;
        }
        
        // 출력
        int ansX = 0, ansY = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                bw.write(map[i][j]+" ");
                
                if (map[i][j] == M) {
                    ansX = i+1;  
                    ansY = j+1;
                }
            }
            bw.write("\n");
        }
        
        bw.write(ansX + " " + ansY);
        bw.flush();
        bw.close();
        br.close();
    }
}

내가 생각한 시간 복잡도: O($N^{2}$)