SWEA : Day 2 (Java)

이번 포스팅에서는 [Ladder1, 달팽이 숫자, 파리퇴치]를 다룹니다

 

1210. Ladder1

import java.io.*;
import java.util.*;
 
public class Solution {
    static int[] dx = { 1, 0, 0 };
    static int[] dy = { 0, -1, 1 };
    static int[][] map = new int[100][100];
    static boolean[][] visited;
 
    static class Pair {
        int first;
        int second;
 
        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
 
    static boolean ladder(int r, int c) {
        Deque<Pair> q = new ArrayDeque<>();
        q.offer(new Pair(r, c));
        visited[r][c] = true;
        int d = 0;
        int x = 0, y = 0;
        while (!q.isEmpty()) {
            x = q.peek().first;
            y = q.peek().second;
            q.poll();
            if (map[x][y] == 2)
                return true;
            if (d == 0) {
     
                for (int dir = 1; dir < 3; dir++) {
                    int nx = x + dx[dir];
                    int ny = y + dy[dir];
                    if (nx < 0 || nx >= 100 || ny < 0 || ny >= 100)
                        continue;
                    if (map[nx][ny] > 0 && visited[nx][ny] == false) {
                        visited[nx][ny] = true;
                        q.offer(new Pair(nx, ny));
                        d = dir;
                        break;
                    }
                }
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (nx < 0 || nx >= 100 || ny < 0 || ny >= 100)
                    continue;
                if (map[nx][ny] > 0 && visited[nx][ny] == false) {
                    visited[nx][ny] = true;
                    q.offer(new Pair(nx, ny));
                }
            } else {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (!(nx < 0 || nx >= 100 || ny < 0 || ny >= 100)) {
                    if (map[nx][ny] > 0 && visited[nx][ny] == false) {
                        visited[nx][ny] = true;
                        q.offer(new Pair(nx, ny));
                    }else {
                        nx = x + dx[0];
                        ny = y + dy[0];
                        if(nx < 0 || nx >= 100 || ny < 0 || ny >= 100) continue;
                        if (map[nx][ny] > 0 && visited[nx][ny] == false) {
                            visited[nx][ny] = true;
                            d = 0;
                            q.offer(new Pair(nx, ny));
                        }
                    }
                }else {
                    nx = x + dx[0];
                    ny = y + dy[0];
                    if(nx < 0 || nx >= 100 || ny < 0 || ny >= 100) continue;
                    if (map[nx][ny] > 0 && visited[nx][ny] == false) {
                        visited[nx][ny] = true;
                        d = 0;
                        q.offer(new Pair(nx, ny));
                    }
                }
            }
        }
        //System.out.println(x + " " + y + " " + map[x][y]);
         
        return false;
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= 10; i++) {
            int T = Integer.parseInt(br.readLine());
            sb.append("#").append(T).append(" ");
            for (int x = 0; x < 100; x++) {
                st = new StringTokenizer(br.readLine());
                for (int y = 0; y < 100; y++) {
                    map[x][y] = Integer.parseInt(st.nextToken());
                }
            }
 
            for (int y = 0; y < 100; y++) {
                if (map[0][y] == 1) {
                    visited = new boolean[100][100];
                    if (ladder(0, y)) {
                        sb.append(y).append("\n");
                    }
                }
            }
        }
        System.out.println(sb.toString());
    }
}

내가 한 방식을 먼저 설명하도록 하겠다. 맨 위부터 시작해서 아래로 가던 중이었다면 항상 좌우를 살피면서 쭉 내려가게 된다. 만약에 좌우에 아무것도 없으면 밑으로 내려가는 방식이다.

또한 오른쪽으로 가던 중이었다면 오른쪽으로 쭉 가게 되고, 만약 오른쪽에 더 길이 없고 아래에 길이 있다면 아래로 전환을 하게 된다. 오른쪽으로 쭉 가다가 맵 끝에 도달하게 되었을 경우 아래에 길이 있는지 확인하고, 길이 있다면 그 방향으로 가게 된다.

 

문제점

도착지와 대응되는 출발지는 단 하나이므로 도착지에서 출발하는 것이 더 간결한 부분이었다. 그렇게 되면 계속 2인지 확인하지 않아도 되는 장점이 있다. 

- 2에 해당하는 (도착지에 해당하는) x와 y 값을 따로 저장한다

- 우선순위가 항상 왼쪽, 오른쪽, 위 순서가 된다. (왼쪽 오른쪽은 같다) 그러므로 for문을 따로 빼주지 않고 dx, dy 배열의 순서를 그렇게 설정하면 된다!...

static int [] dx = {0,0,-1};
static int [] dy = {-1,1,0};
public static void move(int x, int y) {        
   while(true) {
      if(x==0) {
         answer = y;
         break;
      }
      for(int i=0;i<3;i++) {
         int nx = x+dx[i];
         int ny = y+dy[i];
                
         if(range(nx,ny) && map[nx][ny]==1) {
            map[x][y] = 3;
            x = nx; y=ny;
         }
      }
   }
}

 

이 코드에서는 visited 대신 3으로 만들어주어서 왔던 길을 돌아가지 않게 되었다. 나는 계속 visited를 초기화해줘야하는 단점이 있었는데, 밑에서부터 올라가면 답이 하나이기 때문에 map 자체를 변경해도 괜찮은 것이다.

 

 

 

1954. 달팽이 숫자

import java.util.*;
import java.io.*;
public class Solution {
    static int[][] map;
    static int N;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
    static StringBuilder sb;
 
    static void snailGame(int x, int y, int d, int cnt) {
        map[x][y] = ++cnt;
        int nx = x + dx[d];
        int ny = y + dy[d];
        if ((nx < 0 || nx >= N || ny < 0 || ny >= N) || (map[nx][ny] != 0)) {
            d = (d + 1) % 4;
            nx = x + dx[d]; // 회전
            ny = y + dy[d];
            if (map[nx][ny] != 0)
                return;
            snailGame(nx, ny, d, cnt);
        } else if (map[nx][ny] == 0)
            snailGame(nx, ny, d, cnt);
    }
 
    static void printMap() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append("\n");
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            if (N == 1)
                sb.append("1\n");
            else {
                snailGame(0, 0, 0, 0);
                printMap();
            }
        }
        System.out.println(sb.toString());
        br.close();
    }
}

달팽이 숫자와 같은 문제는 굉장히! 삼성 기출에서 쉽게 찾아볼 수 있고 다른 구현 문제나 백준 문제에서도 많이 찾아볼 수 있다. 오른쪽 -> 아래 -> 왼쪽 -> 위 방향으로 빙글빙글 돌기 때문에 dx ,dy를 설정해주고 가려던 방향이 맵의 끝이거나 이미 누군가 들어와있다면 회전을 하도록 하였다. 하지만 다른 분들과 비교해봤을 때 실행시간이 많이 걸렸다...

 

while (c <= n * n) {
    a[i][j] = c++;
    int nx = i + dx[d];
    int ny = j + dy[d];
    if (nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny] != 0) {
       d = (d + 1) % 4;
    }
    i += dx[d];
    j += dy[d];
}

대부분 while 문으로 구현했을 때 훨씬 빨랐다. 재귀호출로 구현하는 것보다 while문으로 달팽이는 구현하는 것이 좋을 것 같다. 

 

 

 

2001. 파리 퇴치

import java.io.*;
import java.util.*;
 
public class Solution{
    static int N, M;
    static int[] dx = { 0, 1 };
    static int[] dy = { 1, 0 };
    static int[][] map;
    static boolean[][] visited;
    static class Pair {
        int first;
        int second;
 
        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
 
    static int catchFly(int r, int c) {
        Deque<Pair> q= new ArrayDeque<>();
        q.offer(new Pair(r, c));
        int sum = 0;
        visited[r][c] = true;
        while(!q.isEmpty()) {
            int x = q.peek().first;
            int y = q.peek().second;
            q.poll();
            sum += map[x][y];
            for(int i = 0; i < 2; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || nx >= r + M || ny < 0 || ny >= c + M) continue;
                if(visited[nx][ny] == true) continue;
                q.offer(new Pair(nx, ny));
                visited[nx][ny] = true;
            }
        }
        return sum;
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuffer sb = new StringBuffer();
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            sb.append("#").append(tc).append(" ");
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            map = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
             
            int ans = 0;
             
            for (int i = 0; i < N-M+1; i++) {
                for (int j = 0; j < N-M+1; j++) {
                    visited = new boolean[N][N];
                    int temp = catchFly(i, j);
                    ans = Math.max(ans, temp);
                }
            }   
            sb.append(ans).append("\n");
        }
        System.out.println(sb.toString());
    }
}

나는 완전 탐색으로 모든 곳에서 더해보는 방식을 사용하였다. 하지만 누적합 배열을 사용한다면 몹시 실행시간을 단축시킬 수 있을 것 같다는 생각이 나중에 들었다.

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

11660번: 구간 합 구하기 5

백준의 구간 합 구하기인데 파리퇴치랑 비슷한 방식이지만 시간제한이 파리퇴치보단 엄격해서 완전 탐색으로 하면 시간초과가 발생한다.

 

map[i][j] = num + map[i-1][j] + map[i][j-1] - map[i-1][j-1];

 

num은 입력받은 값인데 입력받은 값 (map[i][j]의 원래 오리지날 값)에 위와 같이 적용한 모습이다.

for(int i=m; i<=n; ++i) {
     for(int j=m; j<=n; ++j) {
         ans = Math.max(ans, map[i][j] - map[i-m][j] - map[i][j-m] + map[i-m][j-m]); 
     }
}

나중에 파리채 범위를 조정해서 어느 부분의 값이 최대가 되는지 찾으면 된다. 

 

위 그림의 출처 밑 구간합에 대한 자세한 설명은 아래 티스토리를 참조했다

https://propercoding.tistory.com/29

[백준] 11660번 : 구간 합 구하기 5 – JAVA [자바]