MD5

위키백과, 우리 모두의 백과사전.
둘러보기로 가기검색하러 가기

MD5(Message-Digest algorithm 5)는 128비트 암호화 해시 함수이다. RFC 1321로 지정되어 있으며, 주로 프로그램이나 파일이 원본 그대로인지를 확인하는 무결성 검사 등에 사용된다. 1991년에 로널드 라이베스트가 예전에 쓰이던 MD4를 대체하기 위해 고안했다.

1996년에 MD5의 설계상 결함이 발견되었다. 이것은 매우 치명적인 결함은 아니었지만, 암호학자들은 해시 용도로 SHA-1과 같이 다른 안전한 알고리즘을 사용할 것을 권장하기 시작했다. 2004년에는 더욱 심한 암호화 결함[1]이 발견되었고. 2006년에는 노트북 컴퓨터 한 대의 계산 능력으로 1분 내에 해시 충돌을 찾을 정도로 빠른 알고리즘이 발표[2]되기도 하였다. 현재는 MD5 알고리즘을 보안 관련 용도로 쓰는 것은 권장하지 않으며, 심각한 보안 문제를 야기할 수도 있다. 2008년 12월에는 MD5의 결함을 이용해 SSL 인증서를 변조하는 것이 가능하다는 것이 발표되었다[1].

알고리즘[편집]

단일 MD5 연산. MD5에서는 이 단일 연산을 64번 실행한다. 16개의 연산을 그룹화한 4 라운드로 묶인다. F는 각 라운드에서 사용하는 비선형 함수를 가리키며, 각 라운드에서는 각각 다른 함수를 사용한다. Mi는 입력 메시지의 32-비트 블록을 의미한다.

left shifts는 s칸 만큼의 레프트 로테이션을 가리키며, s는 각 연산 후 값이 변한다. Addition 은 모듈로 232 덧셈을 말한다.

MD5는 임의의 길이의 메시지(variable-length message)를 입력받아, 128비트짜리 고정 길이의 출력값을 낸다. 입력 메시지는 512 비트 블록들로 쪼개진다; 메시지를 우선 패딩하여 512로 나누어떨어질 수 있는 길이가 되게 한다. 패딩은 다음과 같이 한다: 우선 첫 단일 비트, 1을 메시지 끝부분에 추가한다. 512의 배수의 길이보다 64 비트가 적은 곳까지 0으로 채운다. 나머지 64 비트는 최초의(오리지널) 메시지의 길이를 나타내는 64 비트 정수(integer)값으로 채워진다.

메인 MD5 알고리즘은 A,B,C,D라고 이름이 붙은 32 비트 워드 네 개로 이루어진 하나의 128 비트 스테이트(state)에 대해 동작한다. A,B,C,D는 소정의 상수값으로 초기화된다. 메인 MD5 알고리즘은 각각의 512 비트짜리 입력 메시지 블록에 대해 차례로 동작한다. 각 512 비트 입력 메시지 블록을 처리하고 나면 128 비트 스테이트(state)의 값이 변하게 된다.

하나의 메시지 블록을 처리하는 것은 4 단계로 나뉜다. 한 단계를 "라운드"(round)라고 부른다; 각 라운드는 비선형 함수 F, 모듈라 덧셈, 레프트 로테이션(left rotation)에 기반한 16개의 동일 연산(similar operations)으로 이루어져 있다. 오른쪽 그림은 한 라운드에서 이루어지는 한 연산(operation)을 묘사하고 있다.

함수 F에는 4가지가 있다; 각 라운드마다 각각 다른 F가 쓰인다:

는 각각 XOR논리곱논리합 그리고 NOT 연산을 의미한다.

의사코드[편집]

MD5 알고리즘의 의사코드는 다음과 같다:

//Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating
var int[64] r, k
//r specifies the per-round shift amounts
r[ 0..15] := {7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22}
r[16..31] := {5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20}
r[32..47] := {4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23}
r[48..63] := {6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21}
//Use binary integer part of the sines of integers as constants:
for i from 0 to 63
    k[i] := floor(abs(sin(i + 1)) × (2 pow 32))
//Initialize variables:
var int h0 := 0x67452301
var int h1 := 0xEFCDAB89
var int h2 := 0x98BADCFE
var int h3 := 0x10325476
//Pre-processing:
append "1" bit to message
append "0" bits until message length in bits ≡ 448 (mod 512)
append bit (bit, not byte) length of unpadded message as 64-bit little-endian integer to message
//Process the message in successive 512-bit chunks:
for each 512-bit chunk of message
    break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15
    //Initialize hash value for this chunk:
    var int a := h0
    var int b := h1
    var int c := h2
    var int d := h3
    //Main loop:
    for i from 0 to 63
        if 0 ≤ i ≤ 15 then
            f := (b and c) or ((not b) and d)
            g := i
        else if 16 ≤ i ≤ 31
            f := (d and b) or ((not d) and c)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            f := b xor c xor d
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            f := c xor (b or (not d))
            g := (7×i) mod 16
        temp := d
        d := c
        c := b
        b := b + leftrotate((a + f + k[i] + w[g]) , r[i])
        a := temp
    //Add this chunk's hash to result so far:
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
var int digest := h0 append h1 append h2 append h3 //(expressed as little-endian)
  //leftrotate function definition
  leftrotate (x, c)
      return (x << c) or (x >> (32-c));
  • 참고: RFC 1321에 나온 공식외에 다음과 같은 공식을 쓰면 퍼포먼스가 향상될 수 있다(어셈블리어가 사용될 때 유용하다 - 다른 언어가 쓰일 경우에는 대개 컴파일러가 위의 코드를 최적화 해준다.)
(0  ≤ i ≤ 15): f := d xor (b and (c xor d))
(16 ≤ i ≤ 31): f := c xor (d and (b xor c))

각주[편집]

  1. 이동 Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger. “MD5 considered harmful today: Creating a rogue CA certificate”.


import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Stack;

import java.util.StringTokenizer;


class Point {

int y, x;


public Point(int y, int x) {

this.y = y;

this.x = x;

}

}


class Process {

int y, x;


public Process(int y, int x) {

this.y = y;

this.x = x;

}


HashSet<Point> moveSet = new HashSet();


public boolean on(int rIndex) {

// 해당 방향으로 전선을 잇는다.


int nextY = y;

int nextX = x;

int endIndex = Solution.MapSize - 1;


while (true) {

nextY += Solution.rotY[rIndex];

nextX += Solution.rotX[rIndex];


if (isRight(nextY, nextX)) {

// 경로기록

moveSet.add(new Point(nextY, nextX));

//경계지점에 도달

if (nextX == 0 || nextY == 0 || nextX == endIndex || nextY == endIndex) {

// 전선연결

for (Point item : moveSet) {

Solution.Visited[item.y][item.x] = 1;

}


return true;

}

} else {

// 경로 삭제

moveSet.clear();

return false;

}

}

}


public boolean isRight(int y, int x) {

if (x < 0 || y < 0 || x >= Solution.MapSize || y >= Solution.MapSize) {

// 배열범위

return false;

} else if (Solution.Visited[y][x] != 0) {

// 해당구획

return false;

}

return true;

}


public void off() {

// 전선을 제거한다.

for (Point item : moveSet) {

Solution.Visited[item.y][item.x] = 0;

}


moveSet.clear();

}


}


class Solution {


static boolean Debug = true;

private static int T;

static int MapSize;


static int[][] Visited; // 시간정보

private static ArrayList<Process> pList;

private static int processLen;

private static int[] checkMin;


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


BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (14).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


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

for (T = 1; T <= TestSize; T++) {


// 맵의 크기

MapSize = Integer.parseInt(br.readLine());


// 프로세스 리스트

pList = new ArrayList<>();

Visited = new int[MapSize][];


// Map 읽기

for (int i = 0; i < MapSize; i++) {

// Map[i] = new int[MapSize];

Visited[i] = new int[MapSize];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < MapSize; j++) {


int item = Integer.parseInt(st.nextToken());

// 맵, Visited 초기화

Visited[i][j] = item == 1 ? 2 : item; // 0:빈공간, 1:방문, 2:프로세스


// 프로세스 등록

if (item == 1) {

boolean inner = i != 0 && j != 0 && i != MapSize - 1 && j != MapSize - 1;

if (inner) {

// 관리 프로세스에 등록

pList.add(new Process(i, j));

}

}


}

}


offProcLen = Integer.MAX_VALUE;

processLen = pList.size();

checkMin = new int[13];


// 최대 값을 저장할 배열

for (int i = 0; i < 13; i++) {

checkMin[i] = Integer.MAX_VALUE;

}


// 탐색

findPath(0, 0);


// 결과 출력

for (int i = 11; i >= 0; i--) {

// 성공한 길이를 탐색

if (checkMin[i] != Integer.MAX_VALUE) {

System.out.println(String.format("#%d %d", T, checkMin[i]));

break;

}

// 그 어떤 전선도 없는 경우

if (i == 0) {

System.out.println(String.format("#%d %d", T, 0));

}

}


}


}


static int offProcLen; // 도달한 0의 개수 (브레이크 조건으로 활용)

static Stack<Integer> debStack = new Stack();


private static void findPath(int index, int bitmask) {


// 끝지점에 도달

if (index == processLen) {


// 0을 몇 번 썼는지 체크

int count_one = countOne(bitmask);

int offLen = processLen - count_one;

if (offProcLen > offLen) {

offProcLen = offLen;

}


// 전선의 길이

int length = 0;

for (Process process : pList) {

length += process.moveSet.size();

}


// 프로세스 개수 별로 최대 개수를 달리한다.

if (checkMin[count_one] > length) {

checkMin[count_one] = length;

}


return;

}


Process item = pList.get(index);


// 프로세스에 전선을 잇는 경우

for (int i = 0; i < 4; i++) {

// 연결이 가능한 경우에만 탐색

int nextBitmask = bitmask + (1 << index);


// 최대 끌 수 있는 프로세스를 고려 (1개까지 꺼서 성공했으면, 2개는 허용 못함)

if (index + 1 - countOne(nextBitmask) <= offProcLen)

if (item.on(i)) {

// debStack.add(i + 1);

findPath(index + 1, nextBitmask);

item.off();

// debStack.pop();

}

}


// 프로세스에 전선을 잇지 않는 경우

// debStack.add(0);

findPath(index + 1, bitmask);

// debStack.pop();


}


static void printMap() {


for (int i = 0; i < MapSize; i++) {

String temp = "";

for (int j = 0; j < MapSize; j++) {

temp += Visited[i][j];

}

log(temp);

}


}


private static int countOne(int bitmask) {


int count = 0;

for (int i = 0; i < processLen; i++) {

if ((bitmask & (1 << i)) != 0) {

count++;

} else {


}

}


return count;

}


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

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


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}

'Knowledge > 알고리즘' 카테고리의 다른 글

[스크랩] MD5 (위키백과)  (0) 2018.06.04
백준 3671번: 산업 스파이의 편지  (0) 2017.10.20
백준 14500번: 테트로미노  (0) 2017.10.20
백준 13460번: 째로탈출2  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.HashSet;

import java.util.StringTokenizer;


public class Main {


private static boolean Debug = true;

private static int PrimeCount;

static int[] pocket;

static HashSet<String> primeSet;

private static int NumberLen;

private static int T;


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


BufferedReader br;


if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

StringTokenizer st;


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

for (T = 0; T < TestLen; T++) {


String NumberStr = br.readLine();

NumberLen = NumberStr.length();

pocket = new int[NumberLen];

for (int i = 0; i < NumberLen; i++) {

pocket[i] = NumberStr.charAt(i) - '0';

}


// 탐색 리스트 초기화

primeSet = new HashSet();

findPath(0, "");

primeSet.remove("");


PrimeCount = 0;

for (String item : primeSet) {

// 소수라면 PrimeCount++

isPrime(Integer.parseInt(item));

}


// 소수의 개수 출력

System.out.println(PrimeCount);

}


}


// 소수 판별

private static boolean isPrime(int num) {


// 2 ~ 제곱근까지 검색

int end = (int) Math.sqrt(num);

for (int i = 2; i <= end; i++) {

if (num % i == 0) {

return false;

}

}


// 2보다 작으면 안되!

if (num < 2) {

return false;

}


PrimeCount++;

return true;

}


private static void findPath(int check, String input) {

// 중복되는 경우는 제거

if (primeSet.contains(input)) {

return;

} else {

primeSet.add(input);

}


// 0인 비트를 골라 1로 채운뒤, 문자열을 조립한다.

for (int i = 0; i < NumberLen; i++) {


int using = 1 << i;


// 시작은 0을 제외한다.

if (check == 0 && pocket[i] == 0) {

continue;

}


if ((check & using) == 0) {

findPath(check + using, input + pocket[i]);

}


}


}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}



import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Map.Entry;

import java.util.StringTokenizer;


class Block {


HashMap<Integer, int[][]> shapeList;

int[][] origin;

int[] flag;

ArrayList<Integer> fList;


// 블록에 해당하는 모양 Data를 만들어줍니다.

public Block(int[][] data, int[] flag) {

this.origin = data;

this.flag = flag;


fList = new ArrayList<>();

for (int item : flag) {

fList.add(item);

}


shapeList = new HashMap<>();

createShape();

// printAllShape();

}


// 회전과 대칭에 따른 데이터(모양) 생성

private void createShape() {


int[][] temp = origin;


// 0번 모양

shapeList.put(0, origin);


// 1~3번 모양(90, 180, 270)

for (int i = 1; i <= 3; i++) {

temp = rotate(temp);

if (fList.contains(i)) {

shapeList.put(i, temp);

}

}


// 4번 모양

int[][] rev = null;

if (fList.contains(4)) {

rev = reverse(origin);

shapeList.put(4, rev);

}


temp = rev;

// 5~7번 모양 rev + (90, 180, 270)

if (fList.contains(5)) {

for (int i = 4; i <= 7; i++) {

temp = rotate(temp);

shapeList.put(i, temp);

}

}


}


// 디버깅을 위한 출력

public void printAllShape() {


int[][] shape;

int ysize, xsize;

for (Entry<Integer, int[][]> entry : shapeList.entrySet()) {


shape = entry.getValue();

ysize = shape.length;

xsize = shape[0].length;


Main.log("[%d]", entry.getKey());


for (int i = 0; i < ysize; i++) {

String line = "";

for (int j = 0; j < xsize; j++) {

line += String.format("%d ", shape[i][j]);

}

Main.log(line);

}

}


}


// 회전 유틸

private int[][] rotate(int[][] data) {

int ysize = data.length;

int xsize = data[0].length;

int end_index = ysize - 1;


int[][] rData = new int[xsize][];

for (int i = 0; i < xsize; i++) {

rData[i] = new int[ysize];

for (int j = 0; j < ysize; j++) {

rData[i][j] = data[end_index - j][i];

}

}


return rData;

}


// 대칭 유틸

private int[][] reverse(int[][] data) {

int ysize = data.length;

int xsize = data[0].length;

int end_index = xsize - 1;


int[][] rData = new int[ysize][];

for (int i = 0; i < ysize; i++) {

rData[i] = new int[xsize];

for (int j = 0; j < xsize; j++) {

rData[i][j] = data[i][end_index - j];

}

}


return rData;

}


}


public class Main {


private static int MapSize_Y;

private static int MapSize_X;

static int[][] Map;


static private ArrayList<Block> bList;


private static boolean Debug = true;

private static int MaxSum;


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


BufferedReader br;


if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

StringTokenizer st;


// 맵 크기

st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


// 맵 데이터 입력

Map = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

st = new StringTokenizer(br.readLine());

Map[i] = new int[MapSize_X];

for (int j = 0; j < MapSize_X; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

}

}


// 블록을 담을 리스트

bList = new ArrayList<>();

Block item; // 블록에는 모양 값들이 저장 된다.


// 블록 모양, 필요한 모양 값 (0: 원형, 1~3: 회전, 4: 대칭, 5~7: 대칭 후 회전)

int[][] 네모Shape = { { 1, 1 }, { 1, 1 } };

item = new Block(네모Shape, new int[] { 0 });

bList.add(item);


int[][] 일자Shape = { { 1, 1, 1, 1 } };

item = new Block(일자Shape, new int[] { 0, 1 });

bList.add(item);


int[][] 산Shape = { { 1, 1, 1 }, { 0, 1, 0 } };

item = new Block(산Shape, new int[] { 0, 1, 2, 3 });

bList.add(item);


int[][] 기역Shape = { { 1, 0 }, { 1, 0 }, { 1, 1 } };

item = new Block(기역Shape, new int[] { 0, 1, 2, 3, 4, 5, 6, 7 });

bList.add(item);


int[][] 어긋Shape = { { 1, 0 }, { 1, 1 }, { 0, 1 } };

item = new Block(어긋Shape, new int[] { 0, 1, 2, 3, 4, 5, 6, 7 });

bList.add(item);


// 완전탐색

MaxSum = -1;

dfs();


// 시간 출력

System.out.println(MaxSum);

}


public static void dfs() {


int blockLen = bList.size();

// 모든 블록에 대한 경우

for (int i = 0; i < blockLen; i++) {

Block block = bList.get(i);


// 각 블록에 따른 데이터를 가져온다. (대칭 및 회전이 포함된 데이터)

for (Entry<Integer, int[][]> item : block.shapeList.entrySet()) {

int[][] data = item.getValue();

int ysize = data.length, xsize = data[0].length;


// 탐색범위 지정(드레그)

int endy, endx;

endy = MapSize_Y - ysize;

endx = MapSize_X - xsize;


// 지정된 탐색 범위에서, data에 맞도록 검색

search(endy, endx, data);

}


}


}


// 해당 블록 모양을 가지고, 해당 위치에서 검색을 해봅니다.

public static void search(int endy, int endx, int[][] data) {


// 탐색 사이즈

int yszie = data.length, xsize = data[0].length;

// 탐색 구간은 (0,0) ~ (endy, endx) 드레그

for (int y = 0; y <= endy; y++) {

for (int x = 0; x <= endx; x++) {


// Block 모양에 따른 탐색

int sum = 0;

for (int i = 0; i < yszie; i++) {

for (int j = 0; j < xsize; j++) {

if (data[i][j] == 1) { // 탐색

sum += Map[y + i][x + j];

}

}

}


// 최대값 판별

if (MaxSum < sum) {

MaxSum = sum;

}


}

}

// log("합: " + sum);

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}



'Knowledge > 알고리즘' 카테고리의 다른 글

1767. [SW Test 샘플문제] 프로세서 연결하기  (0) 2017.10.21
백준 3671번: 산업 스파이의 편지  (0) 2017.10.20
백준 13460번: 째로탈출2  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 3190번: 뱀  (0) 2017.10.19

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.Stack;

import java.util.StringTokenizer;


class Ball {


int y, x;

static int MapSize_Y;

static int MapSize_X;

static int holeY;

static int holeX;


public Ball(int y, int x) {

this.y = y;

this.x = x;


Main.Map[y][x] = 'X'; // 공의 위치 표기

}


public void move(int rIndex) {


int tempY = y;

int tempX = x;

int moveY = y + Main.rotY[rIndex];

int moveX = x + Main.rotX[rIndex];

// 한 방향으로 직진

while (isRight(moveY, moveX)) {

// 성공좌표를 저장 한다.


y = moveY;

x = moveX;


// 전진

moveY += Main.rotY[rIndex];

moveX += Main.rotX[rIndex];

}


// 공의 위치를 변경한다.

Main.Map[tempY][tempX] = '.';

Main.Map[y][x] = isHoll() ? 'O' : 'X';

}


public void move(int inputY, int inputX) {

Main.Map[this.y][this.x] = isHoll() ? 'O' : '.';

this.y = inputY;

this.x = inputX;

Main.Map[this.y][this.x] = isHoll() ? 'O' : 'X';

}


public boolean isRight(int inputY, int inputX) {


if (inputY < 0 || inputX < 0 || inputY >= MapSize_Y || inputX >= MapSize_X) {

// 배열 밖이라면 No

return false;

} else if (isHoll()) {

// 구멍에 있다면 No

return false;

} else if (Main.Map[inputY][inputX] == 'O') {

// 구멍으로 간다면 Yes

return true;

}


// 빈칸이라면 Yes

return Main.Map[inputY][inputX] == '.';

}


public int getXY() {

return y * MapSize_X + x;

}


public boolean isHoll() {

return Ball.holeX == x && Ball.holeY == y;

}


}


public class Main {


private static boolean Debug = true;


private static final int left = 3, right = 1, up = 0, down = 2;

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

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


private static int MapSize_Y;

private static int MapSize_X;

static char[][] Map;

private static int minFindRed;

static Ball rBall;


private static Ball bBall;


private static int[][] Visited;


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


BufferedReader br;


if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

StringTokenizer st;


// 맵 크기, 사과 개수

st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());

Ball.MapSize_Y = MapSize_Y;

Ball.MapSize_X = MapSize_X;


// 맵 생성

Map = new char[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

Map[i] = new char[MapSize_X];

String input = br.readLine();

char item;

for (int j = 0; j < MapSize_X; j++) {


// 맵에 기록, Ball 객체 생성

item = input.charAt(j);

switch (item) {

case 'B':

bBall = new Ball(i, j);

Map[i][j] = 'X';

break;

case 'R':

rBall = new Ball(i, j);

Map[i][j] = 'X';

break;

case 'O':

Ball.holeY = i;

Ball.holeX = j;

Map[i][j] = 'O';

break;

default:

Map[i][j] = item;

break;

}

}

}


// 방문배열 생성 [rBall.getXY()][bBall.getXY()]

int vSize = MapSize_X * MapSize_Y;

Visited = new int[vSize][];

for (int i = 0; i < vSize; i++) {

Visited[i] = new int[vSize];

}


minFindRed = Integer.MAX_VALUE;

// 프레임 체크 (첫 번째 순간은 중복되지 않는다.)

Visited[rBall.getXY()][bBall.getXY()] = 1;


// printMap();

tiltBoard(0);


// 시간 출력

System.out.println(minFindRed == Integer.MAX_VALUE ? -1 : minFindRed);

}


static Stack<Integer> debStack = new Stack();


private static void tiltBoard(int index) {


if (minFindRed <= index) {

// log("탐색불필요 " + debStack);

return;

} else if (bBall.isHoll()) {

// log("[블루볼] " + debStack);

return;

}


// 1.레드볼 여부 && 2. index == 10

if (rBall.isHoll()) { // && !bBall.isHoll() // 위에서 이미 체크

if (minFindRed > index) {

minFindRed = index;

}

// log("[레드볼]" + debStack.toString());

return;

} else if (index == 10) {

// log("[index 10] " + debStack);

return;

}


int redY = rBall.y;

int redX = rBall.x;

int blueY = bBall.y;

int blueX = bBall.x;

for (int i = 0; i < 4; i++) {


// 1. 공을 움직인다.

switch (i) {

case left:

if (redX < blueX) {

rBall.move(i);

bBall.move(i);

} else {

bBall.move(i);

rBall.move(i);

}

break;

case right:

if (redX > blueX) {

rBall.move(i);

bBall.move(i);

} else {

bBall.move(i);

rBall.move(i);

}

break;

case up:

if (redY < blueY) {

rBall.move(i);

bBall.move(i);

} else {

bBall.move(i);

rBall.move(i);

}

break;

case down:

if (redY > blueY) {

rBall.move(i);

bBall.move(i);

} else {

bBall.move(i);

rBall.move(i);

}

break;

}


// 2. 가능한 위치로 이동하여 탐색한다. (좌표 정보는 Ball 객체에 담겨있다.)

// 모두 제자리에 있으면, 탐색X

// 실행됬던 프레임이라면, 탐색X

if (rBall.x == redX && rBall.y == redY && bBall.x == blueX && bBall.y == blueY) {

// non-target

} else if (Visited[rBall.getXY()][bBall.getXY()] == 0) {

Visited[rBall.getXY()][bBall.getXY()] = 1;

// debStack.push(i);


// printMap();

tiltBoard(index + 1);


Visited[rBall.getXY()][bBall.getXY()] = 0;

// debStack.pop();

}


// 3. 공을 원위치로 시킨다.

rBall.move(redY, redX);

bBall.move(blueY, blueX);

}


}


// 디버깅용 프린트 맵

private static void printMap() {


for (int i = 0; i < MapSize_Y; i++) {

String temp = "";

for (int j = 0; j < MapSize_X; j++) {

temp += Map[i][j];

}

if (i == 0) {

temp += "시작";

}

log(temp);

}


}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}



'Knowledge > 알고리즘' 카테고리의 다른 글

백준 3671번: 산업 스파이의 편지  (0) 2017.10.20
백준 14500번: 테트로미노  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 3190번: 뱀  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;


public class Main {


private static boolean Debug = true;

private static int MapSize;

private static int[][] OriginMap;

private static int[][] CopyMap;

private static Queue<Integer>[] bQueue;

static int MaxNum = 0;


final static int north = 0, east = 1, south = 2, west = 3;


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


BufferedReader br;


if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

StringTokenizer st;


// 맵 크기, 사과 개수

MapSize = Integer.parseInt(br.readLine());

MaxNum = 0;


// 맵 생성

OriginMap = new int[MapSize][];

for (int i = 0; i < MapSize; i++) {

OriginMap[i] = new int[MapSize];

st = new StringTokenizer(br.readLine());

int item;

for (int j = 0; j < MapSize; j++) {

item = Integer.parseInt(st.nextToken());

OriginMap[i][j] = item;

// 합칠 수 없는 경우, 처음 주어진 수가 가장 크다.

if (MaxNum < item) {

MaxNum = item;

}

}

}


// 큐 초기화 (블록을 옮기는 데 사용된다.

bQueue = new LinkedList[MapSize];

for (int i = 0; i < MapSize; i++) {

bQueue[i] = new LinkedList<>();

}


// 00000 ~ 33333

int[] bitmasking = new int[5];

execute(bitmasking, 0);


// 시간 출력

System.out.println(MaxNum);

}


private static void execute(int[] bitmask, int index) {


// 비트마스킹을 조립

if (index <= 4) {

for (int i = 0; i < 4; i++) {

bitmask[index] = i;

execute(bitmask, index + 1);

}

return;

}


// 맵초기화

initMap();


// 실행

int rIndex;

for (int i = 0; i < 5; i++) {

rIndex = bitmask[i];

tiltMap(rIndex);

}


}


private static void initMap() {


// Merge를 위한 지도 초기화

CopyMap = new int[MapSize][];

for (int i = 0; i < MapSize; i++) {

CopyMap[i] = new int[MapSize];

for (int j = 0; j < MapSize; j++) {


int num = OriginMap[i][j];

if (num != 0) { // 0은 빈공간

CopyMap[i][j] = num;

} else {

// non-target

}

}

}


}


private static void tiltMap(int rIndex) {

// log("tiltMap(%d)", rIndex);


// 정방향|역방향

// 행기준|열기준

boolean good = (rIndex == west || rIndex == north);

boolean isRow = (rIndex == west || rIndex == east);

// 방향에 따른 병합 및 매칭

int j_start = (good ? 0 : MapSize - 1);

int j_end = (good ? MapSize : -1);

int j_add = (good ? 1 : -1);


for (int i = 0; i < MapSize; i++) {

// 1. 큐에 대입

int j = j_start;

while (j != j_end) {


// 행기준 열기준에 따라 값을 큐에 넣는다. 

int item = isRow ? CopyMap[i][j] : CopyMap[j][i];

if (item != 0) {

bQueue[i].add(item);

// 값을 옮기면, 해당 자리는 빈공간으로 체크

if (isRow) {

CopyMap[i][j] = 0;

} else {

CopyMap[j][i] = 0;

}

}


j += j_add;

}


// 2. 머지

bQueue[i] = mergeBlock(bQueue[i]);


// 3. 맵에 매칭

j = j_start;

while (j != j_end) {

if (!bQueue[i].isEmpty()) {


if (isRow) {

CopyMap[i][j] = bQueue[i].poll();

// log("큐 방출 [%d][%d] = %d", i, j, CopyMap[i][j].num);

} else {

CopyMap[j][i] = bQueue[i].poll();

// log("큐 대입 [%d][%d] = %d", j, i, CopyMap[j][i].num);

}


} else {

break;

}

j += j_add;

}


}


}


static Queue<Integer> rQue;


private static Queue<Integer> mergeBlock(Queue<Integer> que) {


// 반환을 위한 큐

rQue = new LinkedList<>();


// 합치고

int item1 = 0, item2 = 0;

while (true) {


// 합칠 대상1 픽업

if (item1 == 0) {

if (!que.isEmpty()) {

item1 = que.poll();

} else {

// 큐가 비었으므로

break;

}

}


// 합칠 대상2 픽업

if (item2 == 0) {

if (!que.isEmpty()) {

item2 = que.poll();

} else {

// 비교대상이 없으므로

rQue.add(item1);

break;

}

}


// item1과 item2를 합친다.

if (item1 == item2) {


int mergeNum = item1 * 2;

rQue.add(mergeNum);


// 최고값 측정

if (MaxNum < mergeNum) {

MaxNum = mergeNum;

}

item1 = 0;

item2 = 0;

} else { // 합칠수 없는 경우, 이전 비교대상은 rQue에 넣는다.


rQue.add(item1);

item1 = item2; // 다음비교 대상이 첫번 째가 된다.

item2 = 0;

}


}


return rQue;

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}



'Knowledge > 알고리즘' 카테고리의 다른 글

백준 14500번: 테트로미노  (0) 2017.10.20
백준 13460번: 째로탈출2  (0) 2017.10.20
백준 3190번: 뱀  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Hashtable;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;


class Snake {

Queue<Integer> body = new LinkedList<>();


// 해당 위치로 움직인다.

void move(int where, boolean hasApple) {

if (hasApple) {

body.add(where);

} else {

body.poll();

body.add(where);

}

}


// 자기 자신에 충돌하는지 체크한다.

boolean isSelf(int where) {

return body.contains(where);

}

}


public class Main {


private static boolean Debug = false;

private static int MapSize;

private static int[][] Map;

private static Hashtable<Integer, Character> comMap;

private static Snake snake = new Snake();


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


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

StringTokenizer st;


// 맵 크기, 사과 개수

MapSize = Integer.parseInt(br.readLine());

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


// 맵 생성

Map = new int[MapSize][];

for (int i = 0; i < MapSize; i++) {

Map[i] = new int[MapSize];

}


// 사과 위치 배정

int y, x;

for (int i = 0; i < AppSize; i++) {

st = new StringTokenizer(br.readLine());

y = Integer.parseInt(st.nextToken()) - 1;

x = Integer.parseInt(st.nextToken()) - 1;

Map[y][x] = 1;

}


// 커맨드 읽기

comMap = new Hashtable();

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

int time;

char direct;

for (int i = 0; i < cSize; i++) {

st = new StringTokenizer(br.readLine());

time = Integer.parseInt(st.nextToken());

direct = st.nextToken().charAt(0);

comMap.put(time, direct);

}


// 위치 초기화, 시간 초기화

y = x = 0;

rIndex = 1;

timer = 0;


// 뱀이 움직인다.

snake.move(0, false);

findPath();


// 시간 출력

System.out.println(timer);

}


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

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


static int y, x;

static int rIndex;

static int timer;


private static void findPath() {


// 해당 시간에 방향 전환이 발생하는가?

if (comMap.containsKey(timer)) {

char direct = comMap.get(timer);


// 왼쪽 회전 =>  rIndex--;  // 오른쪽 회전 => rIndex++;

if (direct == 'L') {

rIndex = rIndex == 0 ? 3 : rIndex - 1;

} else {

rIndex = rIndex == 3 ? 0 : rIndex + 1;

}

comMap.remove(timer);

}


// 움직임이 시작되는 순간

timer++;


// 움직이려는 방향이 맞다면 움직인다.

if (isVaild(rIndex)) {


y += rotY[rIndex];

x += rotX[rIndex];


int where = y * MapSize + x;

// 자신의 몸에 충돌하는가?

if (snake.isSelf(where)) {

return;

}


// 사과가 있다면

if (Map[y][x] == 1) {

Map[y][x] = 0;

snake.move(where, true);

} else { // 사과가 없다면

snake.move(where, false);

}


findPath();

} else {

// 움직이는 방향이 맵 밖인 경우, 이탈한다.

return;

}


}


// 해당 방향이 맵의 범위를 초과하는지를 판단한다.

private static boolean isVaild(int index) {


switch (index) {

case 0:

return y - 1 >= 0;

case 2:

return y + 1 < MapSize;

case 1:

return x + 1 < MapSize;

case 3:

return x - 1 >= 0;

}


return false;

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}



'Knowledge > 알고리즘' 카테고리의 다른 글

백준 13460번: 째로탈출2  (0) 2017.10.20
백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17
백준 14501번: 퇴사  (0) 2017.10.17

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Dice {

private int[] face;


static final int Left = 1, Right = 2;

static final int Up = 3, Down = 4;


int top, bottom;

int north, south;

int west, east;


// 전개도를 펼쳤을 때, 가운데를 top이라 생각하고, 각각의 면에 index를 메김

public Dice() {

top = 1;

bottom = 6;

north = 2;

south = 5;

west = 4;

east = 3;


face = new int[7];

}


// 주사위 디버깅

private void printDice() {

Main.log("%2d%2d%2d", 0, north, 0);

Main.log("%2d%2d%2d", west, top, east);

Main.log("%2d%2d%2d", 0, south, 0);

Main.log("%2d%2d%2d", 0, bottom, 0);

}


// 주사위를 해당 방향에 굴린 후, 바닥면을 주사위로 옮긴다.

public int move(int direct, int num) {


// 주사위를 굴리면 전개도에서 4면의 변화가 생김

int temp;

switch (direct) {

case Up:

temp = north;

north = top;

top = south;

south = bottom;

bottom = temp;

break;

case Down:

temp = bottom;

bottom = south;

south = top;

top = north;

north = temp;

break;

case Left:

temp = west;

west = top;

top = east;

east = bottom;

bottom = temp;

break;

case Right:

temp = east;

east = top;

top = west;

west = bottom;

bottom = temp;

break;

}


// 윗면 출력

System.out.println(face[top]);

// printDice();


// 주사위 면 복사

int result;

result = face[bottom];

if (num != 0) {

face[bottom] = num;

}


return result;

}


}


public class Main {


private static boolean Debug = false;

private static int MapSize_Y;

private static int MapSize_X;

private static int[][] Map;

private static int[] Command;

private static Dice Dice;

private static int startY;

private static int startX;


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


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

StringTokenizer st;


// 맵 크기

st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


// 주사위 시작 위치

startY = Integer.parseInt(st.nextToken());

startX = Integer.parseInt(st.nextToken());

Command = new int[Integer.parseInt(st.nextToken())];


// 맵 읽기

Map = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

st = new StringTokenizer(br.readLine());

Map[i] = new int[MapSize_X];

for (int j = 0; j < MapSize_X; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

}

}


// 커맨드 읽기

int clen = Command.length;

st = new StringTokenizer(br.readLine());

for (int i = 0; i < clen; i++) {

Command[i] = Integer.parseInt(st.nextToken());

}


Dice = new Dice();


MoveDice();

// System.out.println(MaxSafeCount);

}


// 1~4 동서북남

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

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


private static void MoveDice() {


int clen = Command.length;

int y = startY;

int x = startX;


int moveY, moveX;


for (int i = 0; i < clen; i++) {

int direct = Command[i];

moveY = y + rotY[direct];

moveX = x + rotX[direct];


if (!isRight(moveY, moveX)) {

continue;

}


// 바닥면의 경우

int mapValue = Map[moveY][moveX];

if (mapValue != 0) {

// 바닥에 0이 아닐때, 숫자는 주사위로 옮겨간다.

Dice.move(direct, mapValue);

Map[moveY][moveX] = 0;

} else {

// 바닥이 0이라면 , 숫자는 맵으로 옮겨간다.

int num = Dice.move(direct, mapValue);

Map[moveY][moveX] = num;

}


y = moveY;

x = moveX;

}

}


private static boolean isRight(int y, int x) {


if (x < 0 || y < 0 || x >= MapSize_X || y >= MapSize_Y) {

return false;

} else {

return true;

}

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}



'Knowledge > 알고리즘' 카테고리의 다른 글

백준 12100번: 2048(Easy)  (0) 2017.10.19
백준 3190번: 뱀  (0) 2017.10.19
백준 14502번: 연구소  (0) 2017.10.17
백준 14501번: 퇴사  (0) 2017.10.17
백준 13458번: 시험 감독  (0) 2017.10.17

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.StringTokenizer;


class Virus {

int y, x;


public Virus(int y, int x) {

this.y = y;

this.x = x;

}

}


class Wall {

int y, x;


public Wall(int y, int x) {

this.y = y;

this.x = x;

}

}


public class Main {


private static boolean Debug = true;

private static int MapSize_Y;

private static int MapSize_X;

private static int[][] Map;

private static int[][] Visited;

private static ArrayList<Virus> vList;

private static ArrayList<Wall> wList;

private static int MaxSafeCount;

private static int OriginSafeCount;

private static int VirusCount;


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


BufferedReader br;

StringTokenizer st;


if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


// 맵 크기

st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


vList = new ArrayList<>();

wList = new ArrayList<>();

OriginSafeCount = 0;

// 맵 읽기

int atom;

Map = new int[MapSize_Y][];

Visited = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

st = new StringTokenizer(br.readLine());

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

for (int j = 0; j < MapSize_X; j++) {

atom = Integer.parseInt(st.nextToken());

Map[i][j] = atom;

if (atom == 2) {

vList.add(new Virus(i, j));

OriginSafeCount++;

} else if(atom==0) {

wList.add(new Wall(i, j));

OriginSafeCount++;

}

}

}


MaxSafeCount = 0;

makeWall();

System.out.println(MaxSafeCount);

}


private static void makeWall() {

int wsize = wList.size();


Wall w1, w2, w3;

for (int i = 0; i < wsize; i++) {

for (int j = i + 1; j < wsize; j++) {

for (int k = j + 1; k < wsize; k++) {

w1 = wList.get(i);

w2 = wList.get(j);

w3 = wList.get(k);

Map[w1.y][w1.x] = 1;

Map[w2.y][w2.x] = 1;

Map[w3.y][w3.x] = 1;


simulate();


Map[w1.y][w1.x] = 0;

Map[w2.y][w2.x] = 0;

Map[w3.y][w3.x] = 0;

}

}

}


}


private static void simulate() {


// 조건 초기화

Visited = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

Visited[i] = new int[MapSize_X];

}

// log("s:%d, w:%d, v:%d", countMap(0), countMap(1), countMap(2));


VirusCount = 0;

int y, x;

for (Virus item : vList) {

y = item.y;

x = item.x;


if (Visited[y][x] == 0) {

findPath(y, x);

} else {

// Non-target

}

}


// log("s1:%d, w:%d, v:%d", countMap(0), countMap(1), countMap(2));

int safeCount = countMap(0);

if (MaxSafeCount < safeCount) {

MaxSafeCount = safeCount;

}


}


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

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


private static void findPath(int y, int x) {

Visited[y][x] = 1;

VirusCount++;

if(OriginSafeCount - VirusCount < MaxSafeCount) {

// break; 조건

return;

}

int moveY, moveX;

for (int i = 0; i < 4; i++) {


moveY = y + rotY[i];

moveX = x + rotX[i];


if (isRight(moveY, moveX)) {

findPath(moveY, moveX);

}

}


}


private static boolean isRight(int y, int x) {


if (y < 0 || y >= MapSize_Y || x < 0 || x >= MapSize_X) {

return false;

} else if (Visited[y][x] == 1 || Map[y][x] == 1) {

return false;

}


return true;

}


private static int countMap(int what) {


int count = 0;

for (int i = 0; i < MapSize_Y; i++) {

for (int j = 0; j < MapSize_X; j++) {


if (what == 0) { // 빈공간의 수

if (Visited[i][j] == 0 && Map[i][j] == 0) {

count++;

}

} else if (what == 1) { // 벽의 수

if (Map[i][j] == 1) {

count++;

}

} else if (what == 2) { // 바이러스 영역의 수

if (Visited[i][j] == 1 || Map[i][j] == 2) {

count++;

}

}

}

}


return count;

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}


'Knowledge > 알고리즘' 카테고리의 다른 글

백준 3190번: 뱀  (0) 2017.10.19
백준 14499번: 주사위 굴리기  (0) 2017.10.19
백준 14501번: 퇴사  (0) 2017.10.17
백준 13458번: 시험 감독  (0) 2017.10.17
백준: 14503번: 로봇 청소기  (0) 2017.10.17

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Schedule {

int cost, pay;


public Schedule(int cost, int pay) {

this.cost = cost;

this.pay = pay;

}

}


public class Main {


private static boolean Debug = false;

private static int DateLen;

private static Schedule[] Date;

private static int MaxPayment;


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


BufferedReader br;

StringTokenizer st;


if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


// 일정의 길이

DateLen = Integer.parseInt(br.readLine());

Date = new Schedule[DateLen];


// 일정 읽기

for (int i = 0; i < DateLen; i++) {

st = new StringTokenizer(br.readLine());

Date[i] = new Schedule(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

}


MaxPayment = -1;

checkDate(0, 0);


System.out.println(MaxPayment);

}


private static void checkDate(int index, int sum) {


int cost = Date[index].cost;

int pay = Date[index].pay; 


int next = index + cost;


log("checkDate(%d) sum (%d) next(%d)", index, sum, next);


// 오늘 일정을 사용하고, 다음 일정으로 옮긴다.

if (next < DateLen) {

checkDate(next, sum + pay);

}


// 오늘 일정을 사용하지 않는 경우, 다음 일정으로 옮긴다. (단, 하루짜리 일정은 무조건 체킹)

if (cost != 1 && index + 1 < DateLen) {

checkDate(index + 1, sum);

}


int payment = (next <= DateLen ? sum + pay : sum);

log("최종금액: %d   sum: %d   next: %d", payment, sum, next);

if (MaxPayment < payment) {

MaxPayment = payment;

}


}



public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80


import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


public class Main {


private static boolean Debug = false;

private static int MapSize_Y;

private static int MapSize_X;

private static int[][] Map;

private static int[][] Visited;


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


BufferedReader br;

if (Debug && false) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


// 맵의 크기를 받는다.

st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


// 로봇의 위치를 받는다.

st = new StringTokenizer(br.readLine());

int startY = Integer.parseInt(st.nextToken());

int startX = Integer.parseInt(st.nextToken());

int rIndex = Integer.parseInt(st.nextToken());


// 맵 입력

Map = new int[MapSize_Y][];

Visited = new int[MapSize_Y][];

for (int i = 0; i < MapSize_Y; i++) {

st = new StringTokenizer(br.readLine());

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

for (int j = 0; j < MapSize_X; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

}

}


moveRobot(startY, startX, rIndex);


int count = 0;

for (int i = 0; i < MapSize_Y; i++) {

for (int j = 0; j < MapSize_X; j++) {

if (Visited[i][j] == 1) {

count++;

}

}

}


System.out.println(count);

}


private static int[] rotY = { -1, 0, 1, 0 };

private static int[] rotX = { 0, 1, 0, -1 };


private static void moveRobot(int y, int x, int rIndex) {

Visited[y][x] = 1;

log("(%d,%d) 방문", y, x);


if (!isLeftClear(y, x, rIndex)) {

// Command 1

int nIndex = rIndex == 0 ? 3 : rIndex - 1;

int moveY = y + rotY[nIndex];

int moveX = x + rotX[nIndex];


moveRobot(moveY, moveX, nIndex);

} else if (!isAllClear(y, x)) {

// Command 2

int nIndex = rIndex == 0 ? 3 : rIndex - 1;

moveRobot(y, x, nIndex); // 방향 전환

} else if (isMoveBack(y, x, rIndex)) {

// Command 3

int nIndex = rIndex < 2 ? rIndex + 2 : rIndex - 2;

int moveY = y + rotY[nIndex];

int moveX = x + rotX[nIndex];

moveRobot(moveY, moveX, rIndex); // 방향은 유지한 채로 뒤로 한 발자국

} else {

// Command 4

log("I've Done");

}


}


// 로봇의 왼쪽 방향이 깨끗한지

private static boolean isLeftClear(int y, int x, int rIndex) {

int sIndex = rIndex == 0 ? 3 : rIndex - 1;

int moveY = y + rotY[sIndex];

int moveX = x + rotX[sIndex];


if (moveY < 0 || moveY >= MapSize_Y || moveX < 0 || moveX >= MapSize_X) {

return true;

} else if (Map[moveY][moveX] == 1) {

return true;

} else if (Visited[moveY][moveX] == 1) {

return true;

}


return false;

}


// 모든 방향 모두 깨끗한지

private static boolean isAllClear(int y, int x) {


for (int i = 0; i < 4; i++) {

if (!isLeftClear(y, x, i)) {

return false;

}

}


return true;

}


// 후진이 가능한지

private static boolean isMoveBack(int y, int x, int rIndex) {

int sIndex = rIndex < 2 ? rIndex - 2 + 4 : rIndex - 2;

int moveY = y + rotY[sIndex];

int moveX = x + rotX[sIndex];


if (moveY < 0 || moveY >= MapSize_Y || moveX < 0 || moveX >= MapSize_X) {

return false;

} else if (Map[moveY][moveX] == 1) {

return false;

}


return true;

}


public static void log(String input) {

if(Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if(Debug) {

System.out.println(String.format(input, args));

}

}


}



import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Solution {


static boolean Debug = false;

private static int T;

private static int MapSize_Y;

private static int MapSize_X;

private static int FootSize;


private static int[][] Map; // 맵정보

private static int[][] Visited; // 시간정보

private static int[][] sTunnel; // 현재터널 방위측정

private static int[][] eTunnel; // 다음터널 방위측정


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


BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


eTunnel = new int[8][];

eTunnel[1] = new int[] { 1, 1, 1, 1 };

eTunnel[2] = new int[] { 1, 0, 1, 0 };

eTunnel[3] = new int[] { 0, 1, 0, 1 };

eTunnel[4] = new int[] { 0, 0, 1, 1 };

eTunnel[5] = new int[] { 1, 0, 0, 1 };

eTunnel[6] = new int[] { 1, 1, 0, 0 };

eTunnel[7] = new int[] { 0, 1, 1, 0 };


sTunnel = new int[8][];

sTunnel[1] = new int[] { 1, 1, 1, 1 };

sTunnel[2] = new int[] { 1, 0, 1, 0 };

sTunnel[3] = new int[] { 0, 1, 0, 1 };

sTunnel[4] = new int[] { 1, 1, 0, 0 };

sTunnel[5] = new int[] { 0, 1, 1, 0 };

sTunnel[6] = new int[] { 0, 0, 1, 1 };

sTunnel[7] = new int[] { 1, 0, 0, 1 };


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

for (T = 1; T <= TestSize; T++) {


st = new StringTokenizer(br.readLine());

MapSize_Y = Integer.parseInt(st.nextToken());

MapSize_X = Integer.parseInt(st.nextToken());


int doorY, doorX;

doorY = Integer.parseInt(st.nextToken());

doorX = Integer.parseInt(st.nextToken());


int time = Integer.parseInt(st.nextToken());


Visited = new int[MapSize_Y][];

Map = new int[MapSize_Y][];

// Map 읽기

for (int i = 0; i < MapSize_Y; i++) {

Map[i] = new int[MapSize_X];

Visited[i] = new int[MapSize_X];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < MapSize_X; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

Visited[i][j] = -1;

}

}


findPath(doorY, doorX, time - 1);

FootSize = 0;

for (int i = 0; i < MapSize_Y; i++) {

for (int j = 0; j < MapSize_X; j++) {

if (Visited[i][j] != -1) {

FootSize++;

}

}

}


System.out.println(String.format("#%d %d", T, FootSize));


}


}


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

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


private static void findPath(int y, int x, int time) {

Visited[y][x] = time;


if (time == 0) {

// log(String.format("타임업 - 좌표(%d, %d) 시간: %d", y, x, time));

return;

}


// log(String.format("이동중 - 좌표(%d, %d) 시간: %d", y, x, time));

boolean isLast = true;

int nextY, nextX;

for (int i = 0; i < 4; i++) {

nextY = y + rotY[i];

nextX = x + rotX[i];


// 현재 터널에서 이동 가능한지 체크!

if (sTunnel[Map[y][x]][i] == 0) {

continue;

}


// 다음 경로에 진입할 수 있는지 체크!

if (isRight(nextY, nextX, i, time)) {

findPath(nextY, nextX, time - 1);

isLast = false;

}

}


}


public static boolean isRight(int y, int x, int rIndex, int time) {


if (x < 0 || x >= MapSize_X || y < 0 || y >= MapSize_Y) {

return false; // 배열 범위초과

} else if (Map[y][x] == 0) {

return false; // 벽

} else if (eTunnel[Map[y][x]][rIndex] == 0) {

return false; // 터널 이동 불가

} else if (Visited[y][x] > time) {

// 누군가가 방문했더라면, 나보다 먼저 방문했을 땐 못가고, 내가 더 먼저라면 갈 수 있다.

// 깊이 탐색이므로 시간 순으로 방문하지 않는다. 너비 탐색이라면 알아서 시간 순 탐색이니 신경쓰지 않아도 됨.

return false;

}


return true;

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;


class Solution {


static boolean Debug = false;

private static int T;

private static int MapSize;

private static int[][] Map;

private static int MaxSize;

private static int DesertMaxNo;


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


BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (10).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


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

for (T = 1; T <= TestSize; T++) {


MapSize = Integer.parseInt(br.readLine());

Map = new int[MapSize][];

DesertMaxNo = -1; 


// Map 읽기

for (int i = 0; i < MapSize; i++) {

Map[i] = new int[MapSize];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < MapSize; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

if(Map[i][j]>DesertMaxNo) {

DesertMaxNo = Map[i][j];

}

}

}


MaxSize = -1;

findPath();


System.out.println(String.format("#%d %d", T, MaxSize));


}


}


private static void findPath() {


int y, x;

for (int XY = 0; XY < MapSize * MapSize; XY++) {

// 모든 좌표 탐색


y = XY / MapSize;

x = XY % MapSize;


// 최대 이동범위 구하기 (왼쪽, 오른쪽)

int maxLeft = x;

int maxRight = (MapSize - 1) - x;


for (int i = maxLeft; i > 0; i--) {

for (int j = maxRight; j > 0; j--) {


// 수직크기 측정 (맵의 범위를 벗어나지 않도록)

if (i + j + y >= MapSize) {

continue;

}


// 해당 움직임의 디저트수

int eatSize = (i + j) * 2;

if (MaxSize < eatSize) {

// 더 작은 사이즈는 측정할 필요가 없음

if (eatDesert(XY, i, j) == true) {

MaxSize = eatSize;

}

}


}

}


}


}


// 탐색 순서를 고려하여 배치

static int[] rotY = { 1, 1, -1, -1 };

static int[] rotX = { 1, -1, -1, 1 };


private static boolean eatDesert(int XY, int left, int right) {

// XY: 현재좌표, left: 좌로 움직일 수 있는 범위, right: 우로 움직일수 있는 범위

int y = XY / MapSize;

int x = XY % MapSize;


int[] visited = new int[DesertMaxNo+1];


// ↘ 방향 right 번 -> ↙ 방향 left 번 -> ↖ 방향 right 번 -> ↗ 방향 left번

for (int i = 0; i < right; i++) {

y += rotY[0];

x += rotX[0];


if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}

}


for (int i = 0; i < left; i++) {

y += rotY[1];

x += rotX[1];


if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}


}


for (int i = 0; i < right; i++) {

y += rotY[2];

x += rotX[2];


if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}


}


for (int i = 0; i < left; i++) {

y += rotY[3];

x += rotX[3];


if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}


}


return true;

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

import java.util.StringTokenizer;


class Stair {

int y, x; // 계단의 위치

int cost; // 계단 내려가는데 걸리는 시간

int[] state; // 내려가는 정도

Person[] seat; // 계단 위에 있는 사람들

Queue<Person> inQueue; // 계단 입구

Queue<Person> outQueue; // 계단 출구


public Stair(int y, int x, int cost) {

this.y = y;

this.x = x;

this.cost = cost;


seat = new Person[3];

state = new int[3];

}


public void tick() {


// 작업량 감소 (계단 오르는 비용)

for (int i = 0; i < seat.length; i++) {


if (state[i] != 0 && seat[i] != null) {

state[i]--;

}


}


}


// 계단에서 나간다.

public void comeOut() {


for (int i = 0; i < seat.length; i++) {


if (state[i] == 0 && seat[i] != null) {

outQueue.offer(seat[i]);

seat[i] = null;

}


}


}


// 계단으로 들어온다.

public void comeIn() {


for (int i = 0; i < 3; i++) {

if (seat[i] == null) {

seat[i] = inQueue.poll();

state[i] = cost;

}

}


}


}


class Person {

int y, x;

int time;

int where;


public Person(int y, int x) {

this.y = y;

this.x = x;

}

}


class Solution {


static boolean Debug = false;

private static int T;

private static int MapSize;

private static ArrayList<Person> pList;

private static Stair[] Stair;

private static int PersonSize;

private static int MinTime;


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


BufferedReader br;

if (Debug) {

File f = new File("디렉토리", "sample_input (9).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}


StringTokenizer st;


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

for (T = 1; T <= TestSize; T++) {


MapSize = Integer.parseInt(br.readLine());

pList = new ArrayList<>();

Stair = new Stair[2];


// [Input] 사람 객체를 생성하고 계단 객체를 생성한다.

for (int i = 0; i < MapSize; i++) {

st = new StringTokenizer(br.readLine());

int what;

for (int j = 0; j < MapSize; j++) {

what = Integer.parseInt(st.nextToken());

// 1. 사람이라면

if (what == 1) {

pList.add(new Person(i, j));

} else if (what > 1) { // 2.계단이라면

if (Stair[0] == null) {

Stair[0] = new Stair(i, j, what);

} else if (Stair[1] == null) {

Stair[1] = new Stair(i, j, what);

}

} else {

// Non-target

}

}

}


PersonSize = pList.size();

MinTime = Integer.MAX_VALUE;

// bitmask 값은 각 사람이 어떤 출구로 이동할까를 뜻한다.

for (int i = 0; i < (1 << PersonSize); i++) {

// 각 사람에게 위치와 시간을 지정

schedule(i);

// 시뮬레이션

simulate();

}


System.out.println(String.format("#%d %d", T, MinTime));

}


}


private static void simulate() {


// 0번 계단 입구, 1번 계단 입구, 출구

Queue<Person> Robby0, Robby1, Robby2;

Robby0 = new LinkedList<>();

Robby1 = new LinkedList<>();

Robby2 = new LinkedList<>();


// 계단의 입구와 출구 지정

Stair[0].inQueue = Robby0;

Stair[1].inQueue = Robby1;

Stair[0].outQueue = Robby2;

Stair[1].outQueue = Robby2;


ArrayList<Person> personList = new ArrayList<>();

personList.addAll(pList); // 출입 명단

Stack<Person> dStack = new Stack(); // 출입한 사람은 출입 명단에서 제거


int Timer = -1;

while (Robby2.size() != PersonSize) {

Timer++;


// 사람을 계단입구로 등장시킨다.

for (Person p : personList) {

if (p.time == Timer) {


if (p.where == 0) {

Robby0.offer(p);

} else if (p.where == 1) {

Robby1.offer(p);

}

dStack.add(p);

}

}


// 등장인물 리스트에서 제거

if (!dStack.isEmpty()) {

for (Person p : dStack) {

personList.remove(p);

}

dStack.clear();

}


Stair[0].tick(); // 작업량 감소

Stair[0].comeOut(); // 계단에서 나감

Stair[0].comeIn(); // 계단에 입장


Stair[1].tick();

Stair[1].comeOut();

Stair[1].comeIn();

}


if (MinTime > Timer) {

MinTime = Timer;

}


}


public static void schedule(int bitmask) {

// 상황(bitmask)에 따라서 Person 객체에 시간과 장소를 부여


int y0, x0, y1, x1;

y0 = Stair[0].y;

x0 = Stair[0].x;

y1 = Stair[1].y;

x1 = Stair[1].x;


Person person;

for (int i = 0; i < PersonSize; i++) {


person = pList.get(i);

if ((bitmask & (1 << i)) == 0) {

person.time = getTime(person, y0, x0);

person.where = 0;

// log("0번 출구로 %d만큼의 시간이 걸렸다.", person.time);

} else {

person.time = getTime(person, y1, x1);

person.where = 1;

// log("1번 출구로 %d만큼의 시간이 걸렸다.", person.time);

}


}


}


// xy 지점까지 가는 데 걸리는 시간

public static int getTime(Person p, int y, int x) {

// 계단 입구에 도착하고 1분 후에 내려간다. (1 + 이동시간)

return 1 + (p.x - x > 0 ? p.x - x : x - p.x) + (p.y - y > 0 ? p.y - y : y - p.y);

}


public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}


public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}


}

+ Recent posts