ArrayList를 배열로 바꾸는 방법.
이때 타입을 int 가 아니라 Integer로 선언해주어야 한다.
ArrayList<Integer> int_list = new ArrayList();
Integer arr[] = int_list.toArray(new Integer[int_list.size()]);
ArrayList<String> string_list = new ArrayList();
String arr_2[] = string_list.toArray(new String[string_list.size()]);
| [JAVA] 조합(Combination) 구현 (0) | 2018.11.23 |
|---|---|
| [JAVA] 입력 클래스 (0) | 2018.10.10 |
| [JAVA] 이진탐색트리 (1) | 2018.10.09 |
| [JAVA] Scanner함수 next(), nextLine() 차이 (0) | 2018.09.20 |
문제
https://www.acmicpc.net/problem/14889
i멤버와 j멤버가 같은 팀에 있을 때에 갖는 능력치 배열 Sij가 주어졌을 때, N명의 멤버를 스타트팀과 링크팀 절반으로 나누었을 때 각 팀 능력치 차의 최솟값을 구하는 문제
접근방법
N명 중 N/2명을 고르는 combination 함수를 이용한다.
N명 중 N/2명을 골라 스타트팀에 넣으면 선택되지 않은 멤버는 링크팀에 속하게 된다.
nCr의 조합 경우의 수를 출력하는 것은 아래의 함수를 이용하였다.
static void combination(int[] arr, int index, int n, int r, int target){
if(r == 0){
/* 선택할 r개를 고를 때 마다 실행되는 부분 */
}else if(target == n){
return;
}else {
arr[index] = target;
combination(arr, index+1, n, r-1, target+1);
combination(arr, index, n, r, target +1);
}
}if(r == 0) 부분이 실행되면 배열 arr에 선택한 r개가 담긴다. 이 함수에 담긴 인덱스들은 start[] 배열에 저장하고, 여기에 담기지 않은 인덱스들은 link[] 배열에 저장한다.
구분해주기 위해 boolean check[] 배열을 이용하였다.
이 때, 조합을 절반만 구하면 나머지 절반은 자동으로 다른 팀으로 정해지기 때문에 nCr을 구하는 함수를 절반만 실행하면 된다.
예를 들어 4C2는 (1,2) (1,3) (1,4) (2,3) (2,4) (3,4)가 되는데, (1,2) 를 추출하면 (3,4)는 자동으로 다른 팀이 되므로, (1,2) (1,3) (1,4) 만 구하면된다. 즉, nCr/2 만큼만 조합 경우의 수를 계산하는 함수를 실행해주면 된다.
각 팀의 능력치를 계산한다.
예를 들어 (2, 3, 5) 와 (1, 4, 6) 으로 팀을 나누었을 때, 스타트팀의 능력치는 S(2,3) + S(3,2) + S(2,5) + S(5,2) + S(3,5) + S(5,3)이 된다.
이를 계산해주기 위해 for문을 사용하였다.
for(int i=0; i<N/2; i++)
for(j=i+1; j<N/2; j++){
start_stat += S[start[i]][start[j]] + S[start[j]][start[i]];
link_stat += S[link[i]][link[j]] + S[link[j]][link[i]];
}계산한 능력치의 최소차를 구한다.
소스코드
import java.io.*;
import java.util.*;
public class Main{
static int N;
static int S[][];
static int min_statDiff;
static int count;
// nCr 개수
static int combb(int n, int r) {
if(n == r || r == 0)
return 1;
else
return combb(n - 1, r - 1) + combb(n - 1, r);
}
static void combination(int[] arr, int index, int n, int r, int target){
if(r == 0){
if(count > 0){ // nCr / 2 만큼만 조합 경우의 수 구하기
int cur_statDiff = calcStat(arr);
if(min_statDiff == -1 || cur_statDiff < min_statDiff)
min_statDiff = cur_statDiff;
--count;
}
}else if(target == n){
return;
}else {
arr[index] = target;
combination(arr, index+1, n, r-1, target+1);
combination(arr, index, n, r, target +1);
}
}
static int calcStat(int[] start){
boolean check[] = new boolean[N];
int[] link = new int[N/2];
for(int i=0; i<N/2; i++)
check[start[i]] = true;
int j = 0;
for(int i=0; i<N; i++)
if(check[i] == false)
link[j++] = i;
int start_stat = 0;
int link_stat = 0;
for(int i=0; i<N/2; i++)
for(j=i+1; j<N/2; j++){
start_stat += S[start[i]][start[j]] + S[start[j]][start[i]];
link_stat += S[link[i]][link[j]] + S[link[j]][link[i]];
}
return Math.abs(start_stat - link_stat);
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
S = new int[N][N];
int combi_set[] = new int[N/2];
for(int i=0; i<N; i++){
String line[] = in.readLine().split(" ");
for(int j=0; j<N; j++)
S[i][j] = Integer.parseInt(line[j]);
}
count = combb(N, N/2)/2;
min_statDiff = -1;
combination(combi_set, 0, N, N/2, 0 );
System.out.println(min_statDiff);
}
}| 백준16234 : 인구 이동 (0) | 2018.11.21 |
|---|---|
| 백준15684 : 사다리 조작 (0) | 2018.11.21 |
| [JAVA] 백준 3055 : 탈출 (0) | 2018.09.27 |
| [JAVA] 백준 11559 : 뿌요뿌요 (0) | 2018.09.20 |
| [JAVA] 백준 14503 : 로봇 청소기 (0) | 2018.09.18 |
입력의 범위가 주어지지 않은 경우
백준 5639 문제(https://www.acmicpc.net/problem/5639)를 풀다 입력의 개수가 주어지지 않고 입력이 끝날 때 까지 입력을 받아 처리해야하는 경우를 보았다.
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
for(int i=0; i<N; i++){
/*입력받는 코드*/
}대부분 Scanner를 이용한 위와 같은 방법으로 입력을 처리했기 때문에 java에서 입력을 처리하는 다른 방법을 알아야할 필요성을 느끼게 되었다.
java의 키보드 입력받는 방법
자바에서 키보드의 입력을 받아 처리하는 방법은 크게 두 가지가 있다.
1) Scanner를 이용하는 방법
2) BufferedReader를 이용하는 방법 - 한 줄 단위로 버퍼에서 읽을 수 있는 readLine() 함수가 있으므로, 공백 단위로 입력이 들어올 때에는 StringTokenizer를 이용하여 각각의 문자열을 처리한다.
-> Scanner는 이용은 편리하나, 입력이 여러개가 되면 그 때마다 sc.next~() 함수를 실행해줘야하므로 시간이 많이 소요된다는 단점이 있다.
Scanner의 hasNext() 메소드
boolean hasNext() 메소드는 읽어들일 요소가 있는 여부를 반환한다.
hasNext()로 읽어들일 수 있는 입력이 있다면 true를, 그렇지 않다면 false를 반환한다.
예제는 아래와 같다.
Scanner sc = new Scanner(System.in);
ArrayList<Integer> arr = new ArrayList<>();
while(sc.hasNext()){
arr.add(sc.nextInt());
}
for(int i=0; i<arr.size(); i++)
System.out.println(arr.get(i));BufferedReader을 이용한 입력 처리
BufferedReader는 문자(char)단위로 읽어들이는 InputStreamreader에 버퍼링 기능을 추가한 것으로, 한 번에 입력을 받아들여 버퍼에 저장한 후 사용자가 요구할 때 버퍼에서 읽어온다.
예외를 던질 수 있는 BufferedReader를 사용하기 위해서는 예외를 처리해 주어야한다. (try-catch문 사용 / throw IOException)
백준 15552 : 빠른 A+B 문제
BufferedReader를 이용해 입력을 받고 BufferedWriter를 이용해 결과를 출력하는 문제
1) 먼저 두 객체를 생성해준다.
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));2) BufferedReader를 이용하면 전체의 입력이 버퍼에 저장되므로, 버퍼에서 한 줄씩 읽어오는 readLine() 메소드를 이용한다.
해당 문제에서는 A+B 2개를 입력받기 때문에 String으로 읽고, split함수를 이용해 나눠주었다.
String line = in.readLine();
nums = line.split(" ");
int result = Integer.parseInt(nums[0]) + Integer.parseInt(nums[1]);3) 결과값을 버퍼에 쓴다.
버퍼에 String 값을 쓰는 wirte() 메소드와 개행문자(\n)를 입력하는 newLine() 메소드를 이용하였다.
out.write(String.valueOf(result));
out.newLine();4) 버퍼에 쓴 값을 콘솔에 출력하고, BufferedReader와 BufferedWrite를 닫아준다.
out.flush();
in.close();
out.close();[전체코드]
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
int testcase = Integer.parseInt(in.readLine());
while(testcase > 0){
String nums[] = new String[2];
String line = in.readLine();
nums = line.split(" ");
int result = Integer.parseInt(nums[0]) + Integer.parseInt(nums[1]);
out.write(String.valueOf(result));
out.newLine();
--testcase;
}
out.flush();
in.close();
out.close();
}
}| [JAVA] 조합(Combination) 구현 (0) | 2018.11.23 |
|---|---|
| [JAVA] ArrayList 배열로 바꾸기 (0) | 2018.11.21 |
| [JAVA] 이진탐색트리 (1) | 2018.10.09 |
| [JAVA] Scanner함수 next(), nextLine() 차이 (0) | 2018.09.20 |
이진 탐색 트리란?
이진 탐색 트리(Binary Search Tree)란 부모노드의 값을 기준으로하여 더 작은 값은 왼쪽 자식노드에, 더 큰 값은 오른쪽 자식노드에 이어지는 트리의 형태를 말한다. 탐색하고자 하는 값이 있을 때에는 현재 노드를 중심으로 더 가까운 값들만 골라서 탐색하게 되므로 시간복잡도에서 유리한 시간을 갖는다.
또한 루트노드를 기준으로 자식노드가 연결되므로, 노드가 입력되는 순서에 따라 트리의 모양이 달라진다는 특징을 가진다.
트리 구현
먼저 처음 입력값으로 루트노들르 만들고 그 뒤부터는 노드와의 값을 비교해 탐색하는 노드보다 값이크면 오른쪽 자식노드를, 값이 작다면 왼쪽 자식 노드를 탐색한다. 해당 자식노드가 비어있다면 새로운 노드가 그 위치에 들어가게 되고, 그 노드가 존재한다면, 그 자식노드를 중심으로 함수를 재귀호출하는 방법이다. 코드는 아래와 같다.
소스코드
static class TreeNode{
int value;
TreeNode left;
TreeNode right;
public TreeNode(int v) {value = v;}
}
// 자식노드와 부모노드 연결 함수
static void link_node(TreeNode parent, int value){
// 현재 값이 탐색하고 있는 노드(parent)보다 크다면
// 오른쪽 자식 노드를 탐색
if(value > parent.value){
// 오른쪽 자식 노드가 null 이라면 해당 노드로 연결
if(parent.right == null){
TreeNode newNode = new TreeNode(value);
parent.right = newNode;
} // 오른쪽 자식 노드가 있다면 해당 노드를 탐색노드로 하여 재귀
else{
link_node(parent.right, value);
}
}else{ // 값이 더 작다면 왼쪽 자식 노드 탐색
if(parent.left == null){
TreeNode newNode = new TreeNode(value);
parent.left = newNode;
}else{
link_node(parent.left, value);
}
}
}트리의 순회
1) 전위순회
루트노드를 탐색하고 왼쪽자식노드를 탐색하면 그 단계에서는 왼쪽 자식노드가 루트노드(부모노드)가 되고 그 밑에 있는 자식노드들이 왼쪽자식노드, 오른쪽자식노드가 된다.
// 전위순회 (루트 - 왼 - 오)
static void preorder(TreeNode node){
System.out.print(node.value);
if(node.left != null)
preorder(node.left);
if(node.right != null)
preorder(node.right);
}2) 중위순회
왼쪽자식노드 - 루트노드 - 오른쪽자식노드 순으로 탐색하는 방법이다.
// 중위순회 (왼 - 루트 - 오)
static void inorder(TreeNode node){
if(node.left != null)
inorder(node.left);
System.out.print(node.value);
if(node.right != null)
inorder(node.right);
}3) 후위순회
왼쪽자식노드 - 오른쪽자식노드 - 루트노드 순으로 탐색하는 방법이다.
// 후위순회 (왼 - 오 - 루트)
static void postorder(TreeNode node){
if(node.left != null)
postorder(node.left);
if(node.right != null)
postorder(node.right);
System.out.print(node.value);
}입력을 받아 트리를 만들고 트리를 순회하는 메인함수는 아래와 같다.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
TreeNode root = new TreeNode(sc.nextInt());
for(int i=0; i<N-1; i++)
link_node(root, sc.nextInt());
preorder(root);
System.out.println();
inorder(root);
System.out.println();
preorder(root);
System.out.println();
}| [JAVA] 조합(Combination) 구현 (0) | 2018.11.23 |
|---|---|
| [JAVA] ArrayList 배열로 바꾸기 (0) | 2018.11.21 |
| [JAVA] 입력 클래스 (0) | 2018.10.10 |
| [JAVA] Scanner함수 next(), nextLine() 차이 (0) | 2018.09.20 |
문제
시간이 지날 수록 물이 차오르는 상황에서 고슴도치 집에서 출발한 고슴도치가 친구인 비버 집에 얼마만에 도착할 수 있는가를 구하는 문제. R행 C열로 이뤄진 지도에는 빈칸(.), 물(*), 돌(X), 비버집(D), 고슴도치집(S)이 주어져있다. 매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있고, 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다. 이러한 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 문제.
접근방법
맵의 입력을 숫자로 변환하여 받는다.
빈칸(-2), 물(-1), 돌(2) 고슴도치집(0), 비버집(-100)으로 설정하였다. → 처음 큐에 들어가면서 1씩 증가해야 하므로 고슴도치 집을 0으로 설정하였고, 이와 구분해주기 위해 다른 값들은 위와 같이 설정하였다.
입력을 받으면서 물을 큐에 넣고, 그 뒤에 고슴도치의 위치를 큐에 넣으면서 BFS를 수행한다.
소스코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
static int[] dr = {1, -1, 0, 0};
static int[] dc = {0, 0, 1, -1};
static class Pos{
int r;
int c;
public Pos(int r, int c) {this.r = r; this.c = c;}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
Queue<Pos> queue = new LinkedList<>();
int map[][] = new int[N+2][M+2];
boolean check_doch[][] = new boolean[N+2][M+2];
boolean check_rain[][] = new boolean[N+2][M+2];
// 돌(테두리) 세우기
for(int i=0; i<N+2; i++)
for(int j=0; j<M+2; j++)
map[i][j] = 2; // 1-벽(돌)
Pos dochi = new Pos(0,0);
Pos bibber = new Pos(0,0);
for(int i=1; i<=N; i++){
String line = sc.next();
for(int j=1; j<=M; j++){
char input = line.charAt(j-1);
switch (input){
case '*': // 물
map[i][j] = -1;
queue.offer(new Pos(i, j));
check_rain[i][j] = true;
break;
case 'S': // 고슴도치 집
map[i][j] = 0;
dochi = new Pos(i, j);
break;
case '.': // 빈칸
map[i][j] = -2;
break;
case 'D': // 비버 집
map[i][j] = -100;
bibber = new Pos(i, j);
break;
case 'X': // 돌
map[i][j] = 2;
break;
}
}
}
queue.offer(dochi);
check_doch[dochi.r][dochi.c] = true;
First_Loop:
while(!queue.isEmpty()) {
Pos cur_pos = queue.poll();
for (int i = 0; i < 4; i++) {
Pos next_pos = new Pos(cur_pos.r + dr[i], cur_pos.c + dc[i]);
// 현재 칸이 빗물일 경우 -> 빗물 증가 (방문여부 확인할 필요x)
if (map[cur_pos.r][cur_pos.c] == -1) {
// 주변 칸이 빈칸(-2)일 경우 큐에 넣는다.
if (map[next_pos.r][next_pos.c] == -2) {
map[next_pos.r][next_pos.c] = -1;
check_rain[next_pos.r][next_pos.c] = true;
queue.offer(next_pos);
}
} // 현재 칸이 빈칸일 경우 -> 고슴도치 이동거리 증가
else {
// 주변 칸이 방문하지 않았으면서
if (!check_doch[next_pos.r][next_pos.c]) {
// 비버의 집(-100)일 경우 while문 탈출
if (map[next_pos.r][next_pos.c] == -100){
map[next_pos.r][next_pos.c] = map[cur_pos.r][cur_pos.c] + 1;
break First_Loop;
}// 빈칸(-2)일 경우 계속해서 이동
else if(map[next_pos.r][next_pos.c] == -2){
map[next_pos.r][next_pos.c] = map[cur_pos.r][cur_pos.c] + 1;
check_doch[next_pos.r][next_pos.c] = true;
queue.offer(next_pos);
}
}
}
}
}
if(map[bibber.r][bibber.c] == -100)
System.out.println("KAKTUS");
else
System.out.println(map[bibber.r][bibber.c]);
}
}| 백준15684 : 사다리 조작 (0) | 2018.11.21 |
|---|---|
| 백준14889 : 스타트와 링크 (0) | 2018.11.16 |
| [JAVA] 백준 11559 : 뿌요뿌요 (0) | 2018.09.20 |
| [JAVA] 백준 14503 : 로봇 청소기 (0) | 2018.09.18 |
| [JAVA] 백준 3190 : 뱀 (1) | 2018.09.18 |
문제
뿌요뿌요 룰대로 필드가 주어졌을 때 콤보가 몇 번인지 구하는 문제
- 필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
- 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.
- 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
- 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
- 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
접근방법
4개 이상 붙어있는 것들을 체크한다.
1에 해당하는 뿌요들을 한 번에 없애고 위에 있는 뿌요들을 내려준다.
위 단계를 4개 이상 붙어있는 것이 없을 때까지 반복한다.
1. "4개 이상 붙어있는 것들을 체크한다."
BFS를 사용해 붙어있는 것들을 체크한다.
이 때, 큐를 하나만 사용하면 큐에 있는 것들이 없어지면서(poll) 인접한 배열 원소들을 큐에 넣는 방식이기 때문에, 인접한 원소를 모두 가지고 있을 큐(count_queue)를 하나 더 만든다.
즉, 큐에서 poll() 한 원소를 새로운 큐에 offer() 한다.
새로운 큐의 개수가 4개 이상인지 체크한다.
private static int count(char alpha){
Pos cur_pos;
while(!queue.isEmpty()){
cur_pos = queue.poll();
count_queue.offer(cur_pos);
for(int i=0; i<4; i++){
Pos next_pos = new Pos(cur_pos.r + dr[i], cur_pos.c + dc[i]);
// 동일한 색이면서 아직 방문하지 않았으면 큐에 삽입
if(map[next_pos.r][next_pos.c] == alpha && !check[next_pos.r][next_pos.c]){
check[next_pos.r][next_pos.c] = true;
queue.offer(next_pos);
}
}
}
// count_queue : 붙어있는 뿌요들의 모임
return count_queue.size();
}○ 새로운 큐의 개수가 4개 이상이면 해당 배열 원소를 'd'로 바꿔준다.
1에 해당하는 뿌요들을 한 번에 없애고 위에 있는 뿌요들을 내려준다.
없어질 뿌요 위에 있는 원소들을 하나하나 밑으로 내려준다.
처음에 배열을 (N+2) x (N+2) 로 설정해놓고, 테두리에 '.'로 설정해주었으므로 배열 범위 체크를 따로 해주지 않아도 된다.
private static void deletePuyo(Pos pos){
for(int i=pos.r; i>=1; i--)
map[i][pos.c] = map[i-1][pos.c];
}위 단계를 4개 이상 붙어있는 것이 없을 때까지 반복한다.
1에서 4개 이상의 뿌요가 붙어있다면 isQuit 변수를 true로 바꿔주고, combo를 증가시키기 전 해당 변수를 확인해 false라면 combo를 증가시키지 않고 while문을 빠져나간다.
소스코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
static int dr[] = {1, -1, 0, 0};
static int dc[] = {0, 0, 1, -1};
static int N = 12;
static int M = 6;
static char map[][];
static boolean check[][];
static Queue<Pos> queue;
static Queue<Pos> count_queue;
static class Pos{
int r;
int c;
public Pos(int r, int c) {this.r = r; this.c = c;}
}
private static int count(char alpha){
Pos cur_pos;
while(!queue.isEmpty()){
cur_pos = queue.poll();
count_queue.offer(cur_pos);
for(int i=0; i<4; i++){
Pos next_pos = new Pos(cur_pos.r + dr[i], cur_pos.c + dc[i]);
// 동일한 색이면서 아직 방문하지 않았으면 큐에 삽입
if(map[next_pos.r][next_pos.c] == alpha && !check[next_pos.r][next_pos.c]){
check[next_pos.r][next_pos.c] = true;
queue.offer(next_pos);
}
}
}
// count_queue : 붙어있는 뿌요들의 모임
return count_queue.size();
}
private static void deletePuyo(Pos pos){
for(int i=pos.r; i>=1; i--)
map[i][pos.c] = map[i-1][pos.c];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int combo = 0;
N = 12;
M = 6;
map = new char[N+2][M+2];
check = new boolean[N+2][M+2];
queue = new LinkedList<>();
count_queue = new LinkedList<>();
// 초기화 (테두리 설정)
for(int i=0; i<N+2; i++)
for(int j=0; j<M+2; j++)
map[i][j] = '.';
// 맵 설정
for(int i=1; i<=N; i++){
String line = sc.nextLine();
for(int j=1; j<=M; j++)
map[i][j] = line.charAt(j-1);
}
boolean isQuit = false;
while(true){
isQuit = true;
for(int i=1; i<=N; i++){
for(int j=1; j<=M; j++){
// 배열이 값이 알파벳이면서 아직 체크하지 않았다면 큐에 넣는다.
if(Character.isAlphabetic(map[i][j]) && !check[i][j]){
check[i][j] = true;
queue.offer(new Pos(i, j));
// 붙어있는 동일한 색깔의 뿌요의 개수를 구한다.
int num = count(map[i][j]);
if(num >= 4){
for(int k=0; k<num; k++){
Pos delete = count_queue.poll();
map[delete.r][delete.c] = 'd';
}
// 하나라도 삭제할 게 있으면 while문이 끝나지 않는다.
isQuit = false;
}
count_queue.clear();
}
}
}
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++){
if(map[i][j] == 'd')
deletePuyo(new Pos(i, j));
check[i][j] = false;
}
if(isQuit)
break;
++combo;
}
System.out.println(combo);
}
}| 백준15684 : 사다리 조작 (0) | 2018.11.21 |
|---|---|
| 백준14889 : 스타트와 링크 (0) | 2018.11.16 |
| [JAVA] 백준 3055 : 탈출 (0) | 2018.09.27 |
| [JAVA] 백준 14503 : 로봇 청소기 (0) | 2018.09.18 |
| [JAVA] 백준 3190 : 뱀 (1) | 2018.09.18 |
알고리즘을 풀다보면 예상했던것과 다르게 입력을 받는 경우가 발생한다. 그 중 개행문자('\n')를 먼저 읽어들여 입력한 문자열을 읽어들이지 못하는 경우가 발생한다.
예를 들어,
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
String b = sc.next();
String c = sc.nextLine();
System.out.println(a);
System.out.println(b);
System.out.println(c);그 이유는 next() 함수는 문자단위로 입력을 받으며, nextLine() 함수는 개행문자('\n')가 나올 때 까지의 한 줄을 입력받기 때문이다. 즉, b에서는 문자 그대로 '1234'를 입력받지만, c에서는 1234를 입력하기 전에 입력한 개행문자가 저장이 되는 것이다.
또한 next()는 '문자' 단위로 공백을 입력받지 않고 공백 앞뒤의 문자를 입력받는다. 입출력 예시는 아래와 같다.
| [JAVA] 조합(Combination) 구현 (0) | 2018.11.23 |
|---|---|
| [JAVA] ArrayList 배열로 바꾸기 (0) | 2018.11.21 |
| [JAVA] 입력 클래스 (0) | 2018.10.10 |
| [JAVA] 이진탐색트리 (1) | 2018.10.09 |
문제
로봇 청소기가 있는 장소 N x M 은 빈칸(0) 또는 벽(1)으로 이뤄져있다. 일정한 규칙을 가지고 움직이는 로봇청소기를 이용할 때 청소한 영역의 개수를 구하는 문제이다.로봇청소기의 작동 규칙은 아래와 같다.
현재 위치를 청소한다.
현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
1) 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번 부터 진행한다. 2) 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 3) 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 4) 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
접근방법
- 조건을 그래도 코드로 옮기면 된다. - 청소기의 방향인 북(0), 동(1), 남(2), 서(3) 에서 왼쪽을 보게되면 서(3), 북(0), 동(1), 남(2)을 바라보게 되는데, 이는 switch-case 구문보다 각 방향값에서 1을 빼주는 방법을 사용해 더 깔끔하게 코드를 짤 수 있다.(효근짱b) - 청소기가 네 방향을 모두 탐색한 것은 stay_time 이라는 변수를 두어 해결하였다.
import java.util.Scanner;
public class Main{
static int N;
static int M;
static int map[][];
static int cur_dir;
static class Pos{ int r; int c; }
public static int changDir(int dir){
return (dir == 0)? 3 : dir-1;
}
public static Pos changePos(int dir, Pos pos){
Pos next_pos = new Pos();
next_pos.r = pos.r;
next_pos.c = pos.c;
switch (dir){
case 0: --next_pos.r; break; // 북
case 1: ++next_pos.c; break; // 동
case 2: ++next_pos.r; break; // 남
case 3: --next_pos.c; break; // 서
}
return next_pos;
}
public static Pos backPos(int dir, Pos pos){
Pos next_pos = new Pos();
next_pos.r = pos.r;
next_pos.c = pos.c;
switch (dir){
case 0: ++next_pos.r; break; // 북
case 1: --next_pos.c; break; // 동
case 2: --next_pos.r; break; // 남
case 3: ++next_pos.c; break; // 서
}
return next_pos;
}
public static int cleaning(int map[][], int N, int M, Pos start){
int result = 0;
Pos cur_pos = new Pos();
Pos before_pos = new Pos();
cur_pos.c = before_pos.c = start.c;
cur_pos.r = before_pos.r = start.r;
int stay_time = 0;
while(true){
// 1. 현재 위치를 청소한다.
if(map[cur_pos.r][cur_pos.c] == 0){
map[cur_pos.r][cur_pos.c] = 2;
++result;
//printarr(map);
}
// 2. 현재 위치에서 현재방향을 기준으로 왼쪽부터 탐색을 진행한다.
cur_dir = changDir(cur_dir);
Pos search_pos = changePos(cur_dir, cur_pos);
++stay_time;
// 2-1. 왼쪽방향에 아직 청소하지 않은 공간이 있다면 청소
if(map[search_pos.r][search_pos.c] == 0){
cur_pos.r = search_pos.r; // 현재 위치 변경
cur_pos.c = search_pos.c;
stay_time = 0; // stay time 초기화
}
if(stay_time == 4){
search_pos = backPos(cur_dir, cur_pos);
// 뒤쪽이 벽이면
if(map[search_pos.r][search_pos.c] == 1){
break;
}else{
// 2-3. 후진
cur_pos.r = search_pos.r;
cur_pos.c = search_pos.c;
stay_time = 0;
}
}
}
return result;
}
private static void printarr(int arr[][]){
System.out.println();
for(int i=1; i<arr.length-1; i++){
for(int j=1; j<arr[0].length-1; j++)
System.out.print(map[i][j] + " ");
System.out.println();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
map = new int[N+2][M+2];
for(int i=0; i<N+2; i++)
for(int j=0; j<M+2; j++)
map[i][j] = 1;
Pos start = new Pos();
start.r = sc.nextInt() + 1;
start.c = sc.nextInt() + 1;
cur_dir = sc.nextInt();
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++)
map[i][j] = sc.nextInt();
int result = cleaning(map, N, M, start);
System.out.println(result);
}
}| 백준15684 : 사다리 조작 (0) | 2018.11.21 |
|---|---|
| 백준14889 : 스타트와 링크 (0) | 2018.11.16 |
| [JAVA] 백준 3055 : 탈출 (0) | 2018.09.27 |
| [JAVA] 백준 11559 : 뿌요뿌요 (0) | 2018.09.20 |
| [JAVA] 백준 3190 : 뱀 (1) | 2018.09.18 |
문제
지도에 사과가 놓여있고, 뱀은 명령에 따라 정해진 방향으로 1초에 한 번 씩 움직인다. 뱀이 머리를 움직인 곳에 사과가 있으면 꼬리는 그대로 있으면서 몸의 길이가 늘어나고, 사과가 없으면 꼬리가 있는 칸은 비워줘야한다.
뱀의 처음 몸길이는 1이다.
뱀의 처음위치는 (1,1)이다.
뱀의 처음 이동방향은 오른쪽이다.
사과는 먹고나면 없어진다.
명령은 L, D가 있으며 L은 왼쪽으로, D는 오른쪽으로 90도 방향을 트는 것을 말한다.
예를 들어 현재 방향이 오른쪽이면서 명령이 (3, D)라면, 3초까지 오른쪽으로 이동한 뒤에 4초부터 방향을 90도 틀어 아래로 움직인다.
접근방법
N x N 공간에서 벽을 설정해주기 위해 (N+2) x (N+2) 배열을 만든다.
공간에서 빈칸은 0, 사과는 1, 벽은 2라고 정해놓고 벽을 따로 설정해준다.
// 벽 세팅
for(int i=0; i<N+2; i++)
for(int j=0; j<N+2; j++)
if(i==0 || j==0 || i==N+1 || j==N+1)
map[i][j] = 2;명령어는 X초에 명령 'L' 혹은 'D'가 주어지므로 instruct[X] = 'L' 형식으로 저장한다. 시간을 인덱스로 사용하면 계속해서 경과시간을 나타내는 변수인 time이 증가할 때 참고하기 편하다.
// 명령어 저장
for(int i=0; i<L; i++)
instruct[sc.nextInt()] = sc.next().charAt(0);
뱀이 사과를 먹지 않으면 꼬리부터 없어지기 때문에 FIFO방식의 큐를 이용해 뱀의 몸을 저장한다. 뱀은 머리를 움직일 때 마다 머리가 있는 위치를 큐에 넣어주고, 뱀의 머리가 있는 장소에 사과가 있다면 큐에서 꼬리를 꺼내준다. 또한 뱀의 몸 어느 곳이라도 머리가 부딪히면 게임이 끝나도록 하기 위해 큐에 넣을 때에는 해당 공간을 벽과 동일한 2로 변경해준다. 꼬리를 poll() 할 때 역시 빈칸이 되도록 0으로 변경해준다.
방향 전환은 로봇청소기(14503)과 같이 규칙을 이용한다.
private static int changeDir(int cur_dir, char instruct){
int next_dir;
if(instruct == 'D')
next_dir = (cur_dir==3) ? 0 : ++cur_dir;
else
next_dir = (cur_dir==0)? 3 : --cur_dir;
return next_dir;
}- 즉, 북(↑) 동(→) 남(↓) 서(←)를 0 1 2 3 으로 정하고, 오른쪽으로 90도 꺾어져 이동할 때에는 1씩 증가하고, 왼쪽으로 꺾어질 때에는 1씩 감소하는 규칙을 이용한다. (효근짱!b)
처리하는 순서는 다음과 같다. 1) 시간을 카운트한다. 2) 뱀의 머리 위치를 변경해주고 해당 위치를 큐에 넣는다. 3) 뱀의 머리 위치에 사과가 있는지 확인한다. - 사과가 있다면 아무일도 일어나지 않는다. - 사과가 없다면 큐를 poll() 해준다. 4) 해당 시간에 방g전환 명령이 있는지 확인한다. 명령이 있다면 방향을 바꿔준다.
소스코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
static int dr[] = {-1 ,0, 1, 0};
static int dc[] = {0, 1, 0, -1};
static class Pos{
int r;
int c;
public Pos(int r, int c){this.r = r; this.c = c;}
}
private static int changeDir(int cur_dir, char instruct){
int next_dir;
if(instruct == 'D')
next_dir = (cur_dir==3) ? 0 : ++cur_dir;
else
next_dir = (cur_dir==0)? 3 : --cur_dir;
return next_dir;
}
private static Pos getNextPos(Pos pos, int dir){
Pos next_pos = new Pos(pos.r, pos.c);
switch (dir){
case 0: --next_pos.r; break;
case 1: ++next_pos.c; break;
case 2: ++next_pos.r; break;
case 3: --next_pos.c; break;
}
return next_pos;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 보드 크기 (N x N)
int K = sc.nextInt(); // 사과 개수
int L; // 명령어 개수
int time = 0; // 시간초
int dir = 1; // 이동 방향 (북-0, 동-1, 남-2, 서-3)
Queue<Pos> baam = new LinkedList<>(); // 뱀의 몸 좌표를 넣을 큐
int map[][] = new int[N+2][N+2]; // 보드 (0-빈칸, 1-사과, 2-벽)
char instruct[] = new char[100001]; // 명령
// 벽 세팅
for(int i=0; i<N+2; i++)
for(int j=0; j<N+2; j++)
if(i==0 || j==0 || i==N+1 || j==N+1)
map[i][j] = 2;
// 사과 세팅
for(int i=0; i<K; i++)
map[sc.nextInt()][sc.nextInt()] = 1;
L = sc.nextInt();
// 명령어 저장
for(int i=0; i<L; i++)
instruct[sc.nextInt()] = sc.next().charAt(0);
Pos cur_pos = new Pos(1, 1);
baam.offer(cur_pos);
map[cur_pos.r][cur_pos.c] = 2;
while(true){
++time;
// 뱀의 머리 위치 이동
cur_pos.r += dr[dir];
cur_pos.c += dc[dir];
//cur_pos = getNextPos(cur_pos, dir);
// 벽이나 뱀의 몸을 만났을 경우 게임 종료
if(map[cur_pos.r][cur_pos.c] == 2 ){
break;
}
// 빈칸인 경우 마지막 칸 꼬리를 비워줌
if(map[cur_pos.r][cur_pos.c] == 0){
Pos retail = baam.poll();
map[retail.r][retail.c] = 0;
}
// 머리를 큐에 넣고 맵의 변수 변경
baam.offer(cur_pos);
map[cur_pos.r][cur_pos.c] = 2;
// 방향전환
if(instruct[time] == 'D' || instruct[time] == 'L')
dir = changeDir(dir, instruct[time]);
}
System.out.println(time);
}
}- 예제 2번의 답을 계속 20이라고 생각했던 이유는 뱀이 1초때에 (1,1)에 있고, 2초때 (1,2)로 이동한다고 생각했기 때문. 뱀은 처음에 (1,1)에 있고 1초 때 (1,2)로 이동하므로 time을 0으로 초기화해줘서 해결 할 수 있었다(성희짱!b) -
| 백준15684 : 사다리 조작 (0) | 2018.11.21 |
|---|---|
| 백준14889 : 스타트와 링크 (0) | 2018.11.16 |
| [JAVA] 백준 3055 : 탈출 (0) | 2018.09.27 |
| [JAVA] 백준 11559 : 뿌요뿌요 (0) | 2018.09.20 |
| [JAVA] 백준 14503 : 로봇 청소기 (0) | 2018.09.18 |