easy blog

평이한 수준의 문제였으나 웜홀에 대한 처리가 미숙했다. (44번 case 에서 fail)

아래의 웜홀 검사에서 break를 사용하지 않아, 좌표가 업데이트된 이후, 또다시 원래의 웜홀로 돌아오게 되었다..

무언가를 탐색하고 업데이트를 하면 반드시 루프를 종료할 것.

이런 부분은 정말 찾기가 힘든것 같다. 평소에 주의하여 코딩하는 수 밖에 없다.

                for (P p : wh) {
                    if (p.id == brick && (p.x != x || p.y != y)) {// 웜홀 이동.                    	
                        update(p.x, p.y);
                        break;
                    }
                }

import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;

 
class Solution {
 
    static int N, ans;
    static boolean DBG = false;
    static int[][] map;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    private static int max;
 
    static final int UP = 0;
    static final int DOWN = 1;
    static final int LEFT = 2;
    static final int RIGHT = 3;
 
    static class Ball {
        int x, y;
        int d;// direction
        int cnt;
 
        Ball(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.cnt = 0;
        }
 
        void process(int brick) {
            switch (brick) {
            case 1:
                if (d == UP)
                    d = DOWN;
                else if (d == DOWN)
                    d = RIGHT;
                else if (d == LEFT)
                    d = UP;
                else if (d == RIGHT)
                    d = LEFT;
                count();
                break;
            case 2:
                if (d == UP)
                    d = RIGHT;
                else if (d == DOWN)
                    d = UP;
                else if (d == LEFT)
                    d = DOWN;
                else if (d == RIGHT)
                    d = LEFT;
                count();
                break;
            case 3:
                if (d == UP)
                    d = LEFT;
                else if (d == DOWN)
                    d = UP;
                else if (d == LEFT)
                    d = RIGHT;
                else if (d == RIGHT)
                    d = DOWN;
                count();
                break;
            case 4:
                if (d == UP)
                    d = DOWN;
                else if (d == DOWN)
                    d = LEFT;
                else if (d == LEFT)
                    d = RIGHT;
                else if (d == RIGHT)
                    d = UP;
                count();
                break;
            case 5:
                if (d == UP)
                    d = DOWN;
                else if (d == DOWN)
                    d = UP;
                else if (d == LEFT)
                    d = RIGHT;
                else if (d == RIGHT)
                    d = LEFT;
                count();
                break;
            case 6:
            case 7:
            case 8:
            case 9:
            case 10:
                for (P p : wh) {
                    if (p.id == brick && (p.x != x || p.y != y)) {// 웜홀 이동.                    	
                        update(p.x, p.y);
                        break;
                    }
                }
                break;
            }
        }
 
        public void count() {
            cnt++;
        }
 
        public void update(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    static ArrayList<P> bh, wh;
 
    static class P {
        public int x, y;
        public int id;
 
        P(int x, int y) {
            this.x = x;
            this.y = y;
            this.id = -1;
        }
 
        P(int x, int y, int id) {
            this.x = x;
            this.y = y;
            this.id = id;
        }
    }
 
    public static void main(String args[]) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T;
        T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            max = 0;
            map = new int[N][N];
            wh = new ArrayList<>();
            bh = new ArrayList<>();
            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());
                    if (map[i][j] >= 6 && map[i][j] <= 10) {
                        wh.add(new P(i, j, map[i][j]));
                    }
                    if (map[i][j] == -1) {
                        bh.add(new P(i, j));
                    }
 
                }
            }
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == 0) {
                        int value = simulation(i, j);
                        max = Math.max(value, max);
                    }
                }
            }
            System.out.println("#" + test_case + " " + max);
        }
    }
 
    private static int simulation(int r, int c) {
        int max = 0;
 
        Ball ball;
        // 한지점에서 상하좌우의 이동경우 중, 최대값을 구하여 리턴
        for (int i = 0; i < 4; i++) {
            int nr = r;
            int nc = c;
            ball = new Ball(nr, nc, i);
        
            while (true) {	
                nr = ball.x + dx[ball.d];
                nc = ball.y + dy[ball.d];

                // 경계선인 경우,
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                    // 방향을 변경
                    ball.d = reverseDirection(ball.d);
                    ball.update(nr, nc);
                    ball.count();
                    continue;
                }
 
                // 블랙홀 또는 시작위치인 경우,
                if (map[nr][nc] == -1 || (nr == r && nc == c)) {
                    // 종료
                    max = Math.max(max, ball.cnt);
                    break;
                }
 
                // 빈공간인 경우.
                if (map[nr][nc] == 0) {
                    // 전진
                    ball.update(nr, nc);
                } else {
                    // 이동 후, 기타 블럭 처리
                    ball.update(nr, nc);
                    ball.process(map[nr][nc]);
                }
            }
 
        }
        return max;
    }
 
    static int reverseDirection(int d) {
        if (d == UP)
            return DOWN;
        if (d == DOWN)
            return UP;
        if (d == RIGHT)
            return LEFT;
        return RIGHT;
    }
}

전략

1. Colum 의 인덱스를 중복이 되도록 N개의 순열을 만들어준다. 

2. 만들어진 순열을 Simulation하여 남은 블록을 센다

3. 그중 최소값을 찾는다.

인덱스 삽질로 시간을 허비했다.

제출 후, 47번째 TC에서 fail 했으나 유사한 사례를 검색을 통해 찾게 되었다. (참조 사이트)

map을 만들 때, H를 하나 더 증가시켜서 문제 조건의 하나인 맨 윗칸을 비우는 것을 충족시켰다.

그런데 왜 맨위가 비었다는 이유로 Pass가 되는지는 아직도 모르겠다.

높이가 H인 경우의 반례를 생각해보려 했으나 코드 동작상 아무런 차이가 없다.

import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Solution {

	static int N, H, W;
	static boolean DBG = false;
	static int[][] map, dummy;
	private static int ans;
	static int totalBricks;
	static int dummyTotalBricks;

	public static void main(String args[]) throws Exception {

		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		/*
		File file = new File(
				"C:\\Users\\Lee\\eclipse-workspace\\TestApplication\\src\\com\\test\\testapplication\\output.txt");
		PrintStream ps = new PrintStream(file);
		System.setOut(ps);
		 */

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			totalBricks=0;
			ans = Integer.MAX_VALUE;
			map = new int[H+1][W];
			
			for (int i = 1; i <= H; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if (map[i][j] != 0)
						++totalBricks;
				}
			}
			go(0, new int[N]);
			// UnitTest();
			System.out.println("#" + test_case + " " + ans);
		}
	}

	// 중복 순열 : [0,W]사이의 인덱스를 선택하는 경우의 수,
	private static void go(int level,  int[] perm) {
		if (level == N) {
			if (DBG) {
				StringBuilder sb = new StringBuilder();
				for (int v : perm) {
					sb.append(v).append(' ');
				}
				System.out.println(sb);
			}

			dummy = new int[H+1][W];

			for (int i = 0; i <= H; i++) {
				dummy[i] = Arrays.copyOf(map[i], W);
			}

			int rest = simulation(perm);
			ans = Math.min(rest, ans);

		} else {
			for (int i = 0; i < W; i++) {
				perm[level] = i;
				go(level + 1, perm);
			}

		}
	}

	private static void UnitTest() {
		dummy = new int[H+1][W];

		for (int i = 0; i <= H; i++) {
			dummy[i] = Arrays.copyOf(map[i], W);
		}

		int[] perm = new int[3];
		perm[0] = 2;
		perm[1] = 2;
		perm[2] = 6;
		int rest = simulation(perm);
		sort();
		ans = Math.min(rest, ans);

	}

	private static int simulation(int[] perm) {
		dummyTotalBricks = totalBricks;
		for (int i = 0; i < perm.length/* N */ ; i++) {
			int c = perm[i];
			if (DBG)
				System.out.printf("perm[%d] c : %d\n", i, perm[i]);
			for (int r = 0; r <= H; r++) {
				if (dummy[r][c] == 0)
					continue;
				// 스플레시
				int width = dummy[r][c];
				explode(r, c, width);

				if (DBG) {
					System.out.printf("r : %d c: %d width : %d dummyTotalBricks : %d\n", r, c, width, dummyTotalBricks);
					for (int[] ar : dummy) {
						for (int v : ar) {
							System.out.print(v + " ");
						}
						System.out.println();
					}
				}

				sort();
				if (DBG) {
					System.out.println("after sort");
					for (int[] ar : dummy) {
						for (int v : ar) {
							System.out.print(v + " ");
						}
						System.out.println();
					}
				}
				break;
			}
		}
		return dummyTotalBricks;
	}

	private static void sort() {
		// 블록들을 정리한다.
		for (int i = 0; i < W; i++) {
			for (int j = H; j > 1; j--) {
				if (dummy[j][i] == 0) {
					for (int k = j - 1; 0 <= k; k--) {
						if (dummy[k][i] != 0) {
							dummy[j][i] = dummy[k][i];
							dummy[k][i] = 0;
							break;
						}
					}
				}
			}
		}
	}

	static int[] dx = { 0, 0, -1, 1 };
	static int[] dy = { 1, -1, 0, 0 };

	private static void explode(int r, int c, int width) {

		// 현재 터진 자리를 0으로 지운다.
		dummy[r][c] = 0;
		if (DBG)
			System.out.printf("set 0 %d %d %d\n", r, c, dummy[r][c]);
		// 터질 때마다 남은 블록수를 count한다.
		dummyTotalBricks--;

		for (int d = 0; d < 4; d++) {
			for (int w = 1; w < width; w++) {
				// 폭발의 범위내에 터질 블록이 있으면 폭파 시킨다.
				int nr = r + w * dx[d];
				int nc = c + w * dy[d];
				if (nr >= 0 && nr <= H && nc >= 0 && nc < W && dummy[nr][nc] != 0) {
					int nWidth = dummy[nr][nc];
					explode(nr, nc, nWidth);
				}
			}
		}
	}

}

참조 : https://jongnan.tistory.com/entry/SW-Expert-5656-%EB%B2%BD%EB%8F%8C-%EA%B9%A8%EA%B8%B0

모의 테스트 문제중 제일 쉬운 문제 같다.

rotation => right or left shift -> substring(1,len) + s.charAt(0);

Hex String -> Integer.parseInt( K th value, 16 );

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Solution {

	static int N, K, W;

	private static boolean DBG = false;
	static String s;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;

		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			s = br.readLine();

			W = N / 4;
			ArrayList<String> answer = new ArrayList<>();

			for (int t = 0; t < W; t++) {
				for (int i = 0; i < N; i += W) {
					String sub = s.substring(i, i + W);
					if (!answer.contains(sub))
						answer.add(sub);
				}
				s = rightShift();
				
			}

			Collections.sort(answer, Collections.reverseOrder());
		
			if(DBG) {
				for (String str : answer) {
					System.out.print(str + " ");
				}
				System.out.println();
			}
			
			
			System.out.println("#" + test_case + " "+Integer.parseInt(answer.get(K-1),16));
		}
	}

	private static String rightShift() {
		StringBuilder sb = new StringBuilder();
		return sb.append(s.charAt(s.length()-1)).append(s.substring(0, s.length()-1)).toString();
	}

}