Lombok 라이브러리에서 제공하는 어노테이션 중에서 자주 사용되는 어노테이션 위주로 살펴보도록 하겠습니다.

접근자/설정자 자동 생성

제일 먼저 살펴볼 어노테이션은 @Getter와 @Setter 입니다. 아마 Lombok에서 가장 많이 사용되는 어노테이션일 텐데요. 예를 들어, xxx라는 필드에 선언하면 자동으로 getXxx()(boolean 타입인 경우, isXxx())와 setXxx() 메소드를 생성해줍니다.

@Getter @Setter
private String name;

위와 같이 특정 필드에 어노테이션을 붙여주면, 다음과 같이 자동으로 생성된 접근자와 설정자 메소드를 사용할 수 있어서 매우 편리합니다.

user.setName("홍길동");
String userName = user.getName();

또한, 필드 레벨이 아닌 클래스 레벨에 @Getter 또는 @Setter를 선언해줄 경우, 모든 필드에 접근자와 설정자가 자동으로 생성됩니다.

VO 클래스를 작성할 때 마다, 접근자와 설정자 메소드를 작성해주는게 참 번거로운 일이었는데, (특히, 수정할 때는 더욱이) Lombok을 쓰게되면 이런 노가다성 코딩에서 해방될 수 있습니다. :)

생성자 자동 생성

Lombok을 사용하면 생성자도 자동으로 생성할 수 있습니다. @NoArgsConstructor 어노테이션은 파라미터가 없는 기본 생성자를 생성해주고, @AllArgsConstructor 어노테이션은 모든 필드 값을 파라미터로 받는 생성자를 만들어줍니다. 마지막으로 @RequiredArgsConstructor 어노테이션은 final이나 @NonNull인 필드 값만 파라미터로 받는 생성자를 만들어줍니다.

@NoArgsConstructor
@RequiredArgsConstructor
@AllArgsConstructor
public class User {
  private Long id;
  @NonNull
  private String username;
  @NonNull
  private String password;
  private int[] scores;
}
 
User user1 = new User();
User user2 = new User("dale", "1234");
User user3 = new User(1L, "dale", "1234", null);

ToString 메소드 자동 생성

toString() 메소드를 작성하는 것도 여간 귀찮은 일이 아닙니다. 하지만 Lombok을 사용하면 @ToString 어노테이션만 클래스에 붙여주면 자동으로 생성해줍니다.

예제와 같이 exclude 속성을 사용하면, 특정 필드를 toString() 결과에서 제외시킬 수도 있습니다.

 
@ToString(exclude = "password")
public class User {
  private Long id;
  private String username;
  private String password;
  private int[] scores;
}

위와 같이 클래스에 @ToString 어노테이션을 붙이고, 아래와 같이 필드를 세팅 후 출력을 하면,

User user = new User();
user.setId(1L);
user.setUsername("dale");
user.setUsername("1234");
user.setScores(new int[]{80, 70, 100});
System.out.println(user);

다음과 같이, 클래스명(필드1명=필드1값,필드2명=필드2값,...) 식으로 출력됩니다.

User(id=1, username=1234, scores=[80, 70, 100])

Lombok을 사용하기 전에는 Apache Commons Lang 라이브러리의 ToStringBuilder를 사용했었는데, Lombok을 사용하는 게 어노테이션 한 방으로 끝나니 훨씬 편한 것 같습니다.

equals, hashCode 자동 생성

자바 빈을 만들 때 equals와 hashCode 메소드를 자주 오버라이딩 하는데요. @EqualsAndHashCode 어노테이션을 사용하면 자동으로 이 메소드를 생성할 수 있습니다.

@EqualsAndHashCode(callSuper = true)
public class User extends Domain {
  private String username;
  private String password;
}
 

callSuper 속성을 통해 equals와 hashCode 메소드 자동 생성 시 부모 클래스의 필드까지 감안할지 안 할지에 대해서 설정할 수 있습니다.

즉, callSuper = true로 설정하면 부모 클래스 필드 값들도 동일한지 체크하며, callSuper = false로 설정(기본값)하면 자신 클래스의 필드 값들만 고려합니다.

User user1 = new User();
user1.setId(1L);
user1.setUsername("user");
user1.setPassword("pass");

User user2 = new User();
user1.setId(2L); // 부모 클래스의 필드가 다름
user2.setUsername("user");
user2.setPassword("pass");

user1.equals(user2);
// callSuper = true 이면 false, callSuper = false 이면 true

끝판왕! @Data

@Data는 위에서 설명드린 @Getter, @Setter, @RequiredArgsConstructor, @ToString, @EqualsAndHashCode을 한꺼번에 설정해주는 매우 유용한 어노테이션입니다.

@Data
public class User {
  // ...
}

사용 방법은 다른 어노테이션들과 대동소이합니다. 클래스 레벨에서 @Data 어노테이션을 붙여주면, 모든 필드를 대상으로 접근자와 설정자가 자동으로 생성되고, final 또는 @NonNull 필드 값을 파라미터로 받는 생성자가 만들어지며, toStirng, equals, hashCode 메소드가 자동으로 만들어집니다.

이상으로 자주 사용되는 Lombok 어노테이션에 대해서 살펴보았습니다. 다음 포스팅에서는 많이 알려지지는 않았지만 알아두면 유용한 Lombok 어노테이션에 대해서 알아보겠습니다.

크로스도메인 이슈란?

Ajax 등을 통해 다른 도메인의 서버에 url(data)를 호출할 경우 XMLHttpRequest는 보안상의 이유로 자신과 동일한 도메인으로만 HTTP요청을 보내도록 제한하고 있어 에러가 발생한다.
내가 만든 웹서비스에서 사용하기 위한 rest api 서버를 무분별하게 다른 도메인에서 접근하여 사용하게 한다면 보안상 문제가 될 수 있기 때문에 제한하였지만 지속적으로 웹 애플리케이션을 개선하고 쉽게 개발하기 위해서는 이러한 request가 꼭 필요하였기에 그래서 XMLHttpRequest가 cross-domain을 요청할 수 있도록하는 방법이 고안되었다.
그것이 CORS 이다.

CORS란?

CORS(Cross-origin resource sharing)이란, 웹 페이지의 제한된 자원을 외부 도메인에서 접근을 허용해주는 메커니즘이다.

스프링에서 CORS 설정하기.

스프링 RESTful Service에서 CORS를 설정은 @CrossOrigin 어노테이션을 사용하여 간단히 해결 할 수 있다. RestController를 사용한 클래스 자체에 적용할 수 도 있고, 특정 REST API method에도 설정 가능하다.
또한, 특정 도메인만 접속을 허용할 수도 있다.

사용예 )

@CrossOrigin(origins = “허용주소:포트”)

예제코드 1)

  • WebMvcConfigurer를 통해 적용하는 방식.
package io.jmlim.corssample.corssample;
 
import org.springframework.context.annotation.Configuration;
import org.springframework.web.servlet.config.annotation.CorsRegistry;
import org.springframework.web.servlet.config.annotation.WebMvcConfigurer;

@Configuration
public class WebConfig implements WebMvcConfigurer {

    @Override
    public void addCorsMappings(CorsRegistry registry) {
      // 모든 uri에 대해 http://localhost:18080, http://localhost:8180 도메인은 접근을 허용한다.
        registry.addMapping("/**")
                .allowedOrigins("http://localhost:18080","http://localhost:8180");

    }
}

예제코드 2)

  • @CrossOrigin 어노테이션을 통해 적용하는 방식.
package io.jmlim.corssample.corssample;

 
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.web.bind.annotation.CrossOrigin;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

@SpringBootApplication
//해당 컨트롤러의 모든 요청에 대한 접근 허용(아래 도메인 두개에 대해서만..)
@CrossOrigin(origins = {"http://localhost:18080", "http://localhost:8180" }) 
@RestController
public class CorssampleApplication {
 
	//아래와 같이 특정 메소드에만 적용할수도 있다.
    //@CrossOrigin(origins = {"http://localhost:18080", "http://localhost:8180" })
    @GetMapping("/hello")
    public String hello() {
        return "hello";
    }
	
	@GetMapping("/my")
    public String my() {
        return "my";
    }
	
 
    public static void main(String[] args) {
        SpringApplication.run(CorssampleApplication.class, args);
    }
}

예제코드 호출하기

만약 이 코드가 실행되는 웹서버의 도메인이 http://localhost:18080과 http://localhost:8080이 아닐경우 fail이 발생한다.

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>

    <script
           src="https://code.jquery.com/jquery-3.3.1.js"
            integrity="sha256-2Kok7MbOyxpgUVvAk/HJ2jigOSYS2auK4Pfzbm7uH60="
            crossorigin="anonymous"></script>
    <script>
       // alert(1);
        $(function() {
			  // 만약 이 코드가 실행되는 웹서버의 도메인이 http://localhost:18080과 http://localhost:8080이 아닐경우 fail이 발생한다.
            $.ajax("http://localhost:8180/hello")
                .done(function(msg) {
                    alert(msg);
                }).fail(function() {
                    alert("fail");
                });
        });
    </script>
</head>
<body>

</body>
</html>

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

 

11047번: 동전 0

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

www.acmicpc.net


그리디 알고리즘을 활용한 단순한 문제이다.
가장 큰수 부터 나눠지는대로 나눠서 몫을 cnt 값에 더해주기만 하면 끝이다.


 

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

public class Main {

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int cnt = 0;

		int[] A = new int[N];

		for (int i = 0; i < N; i++)
			A[i] = Integer.parseInt(br.readLine());

		for (int i = N - 1; 0 <= i; i--) {
			int quotient = K / A[i]; // 몫

			if (quotient == 0)
				continue;
			else {
				K = K - A[i] * quotient;
				cnt += quotient;
			}
		}
		System.out.println(cnt);
	}
}

 

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

 

4949번: 균형잡힌 세상

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다

www.acmicpc.net


풀이 

어렵게 생각하면 어렵고 쉽게 생각하면 쉬운 문제였다.
많은 문자열을 입력받지만, 우리가 생각해야될 것은 괄호 뿐이므로 '(', ')', '[', ']'가 들어오는 경우만
생각해주면 된다.

'(' , '['이 들어오는 경우는 Stack에 Push 하였고
')', ']' 이 들어오는 경우는 앞에 여는 괄호가 일치한지만 판단하여 pop하였다.

 

기타

풀다가 문자열을 비교할 때 equals 와 == 차이가 궁금해서 글로 한번 요약 정리 해보았다.

https://studywithus.tistory.com/88

 

[JAVA] 문자열 비교하기 String에서 ==와 equals 의 차이

Java에서 int와 boolean과 같은 일반적인 데이터 타입의 비교는 ==이라는 연산자를 사용하여 비교합니다. 하지만 String처럼 Class의 값을 비교할때는 ==이 아닌 equals()라는 메소드를 사용하여 비교를 합

studywithus.tistory.com

 


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		while (true) {
			String input = br.readLine();

			if (input.equals("."))
				break;

			sb.append(solve(input) + '\n');
		}
		System.out.println(sb);
	}

	static String solve(String input) {

		Stack<Character> stack = new Stack<Character>();

		for (int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);

			if (c == '(' || c == '[')
				stack.push(c);

			if (c == ')') {
				if (stack.isEmpty() || stack.peek() != '(')
					return "no";
				else
					stack.pop();
			}

			if (c == ']') {
				if (stack.isEmpty() || stack.peek() != '[')
					return "no";
				else
					stack.pop();
			}
		}

		if (stack.isEmpty())
			return "yes";
		else
			return "no";
	}
}

Java에서 int와 boolean과 같은 일반적인 데이터 타입의 비교는 ==이라는 연산자를 사용하여 비교합니다. 하지만 String처럼 Class의 값을 비교할때는 ==이 아닌 equals()라는 메소드를 사용하여 비교를 합니다. equals와 == 은 어떤 차이점이 있을까요.

String 변수 생성시 주소할당

String변수를 생성할때는 두가지 방법이 있습니다.

1. 리터럴을 이용한 방식 
2. new 연산자를 이용한 방식 

 

위의 두 가지 방식에는 큰 차이점이 있습니다. 리터럴을 사용하게 되면 string constant pool이라는 영역에 존재하게 되고 new를 통해 String을 생성하면 Heap 영역에 존재하게 됩니다. String을 리터럴로 선언할 경우 내부적으로 String의 intern() 메서드가 호출되게 되고 intern() 메서드는 주어진 문자열이 string constant pool에 존재하는지 검색하고 있다면 그 주소값을 반환하고 없다면 string constant pool에 넣고 새로운 주소값을 반환합니다. 

 

여기서 String pool 이란?

Pool 하면 보통 수영장 풀, 풀장 등을 떠올리실 텐데요. 이처럼 String pool 하면 string이 존재하는 영역을 생각하시면 될 것 같습니다. 같은 String이지만 생성 방식에 따라 차이가 있어 문자열 비교 시 혼란을 주기도 하는데요. 다음 예제를 통해 설명해보겠습니다.

String a = "apple";
String b = new String("apple");
String c = "apple";
String d = new String("apple");

System.out.println(a==b); // false
System.out.prrintln(a==c); // true

 

첫 번째 줄에서 String a가 생성될 때, 'apple'은 리터럴 문자열이므로 Heap영역 중에서 String pool에 위치하게 됩니다.
두 번째 줄에서 String b는 new 연산자를 통해 객체를 생성합니다. Heap영역에 위치하지만 String pool이 아닌 다른 주소값을 참조합니다.

'=='연산자는 같은 메모리를 참조하는가를 비교합니다. 때문에  a와 b의 비교(a==b)는 false를 반환하게 됩니다.

그렇다면 c는 어떨까요? c가 가리키는 'apple'을 String pool에 넣으려고 보니 이미 'apple'이 존재합니다. 그러면 c는 a와 같은 String pool의 'apple'을 가리키게 됩니다.

a와 c가 같은 값을 참조하므로 a==c는 true를 반환합니다.

이를 그림으로 표현해보면 다음과 같습니다.

 

 

주소값 비교(==)와 값 비교(equals)

==연산자와 equals()메소드의 가장 큰 차이점은 == 연산자는 비교하고자 하는 두개의 대상의 주소값을 비교하는데 반해 String클래스의 equals 메소드는 비교하고자 하는 두개의 대상의 값 자체를 비교한다는 것입니다. 기본 타입의 int형, char형등은 Call by Value 형태로 기본적으로 대상에 주소값을 가지지 않는 형태로 사용됩니다. 하지만 String은 일반적인 타입이 아니라 클래스입니다. 클래스는 기본적으로 Call by Reference형태로 생성 시 주소값이 부여됩니다. 그렇기에 String타입을 선언했을때는 같은 값을 부여하더라도 서로간의 주소값이 다릅니다.

 

문자열 비교 (==연산자)

public class compare {
    public static void main(String[] args) {
        String s1 = "abcd";
        String s2 = new String("abcd");
		
        if(s1 == s2) {
            System.out.println("두개의 값이 같습니다.");
        }else {
            System.out.println("두개의 값이 같지 않습니다.");
        }
    }
}

위의 결과를 보시면 ==으로 비교한 두개의 값은 서로 다르다는 결론이 나오게 됩니다. == 연산자의 경우 참조 타입 변수들 간의 연산은 동일한 객체를 참조하는지, 다른 객체를 참조하는지 알아볼 때 사용됩니다. 참조 타입의 변수의 값은 힙 영역의 객체 주소이므로 결국 주소 값을 비교하는 것이 되어 다르다는 결론이 나온것입니다. 그래서 자바에서 문자열을 비교하려면 equals라는 메서드를 활용하여 두개의 값을 비교해주어야 합니다.

 

문자열 비교 (equals메서드)

public class compare {
    public static void main(String[] args) {
        String s1 = "abcd";
        String s2 = new String("abcd");
		
        if(s1.equals(s2)) {
            System.out.println("두개의 값이 같습니다.");
        }else {
            System.out.println("두개의 값이 같지 않습니다.");
        }
    }
}

String 클래스안에 있는 equals라는 메서드를 사용하면 두 비교대상의 주소 값이 아닌 데이터값을 비교하기 때문에 어떻게 String을 생성하느냐에 따라 결과가 달라지지 않고 정확한 비교를 할 수 있습니다.

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

 

2477번: 참외밭

첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지

www.acmicpc.net

 


풀이 

처음에는 간단하게 생각해서 ( 전체 큰 사각형 - 작은 사각형 ) 빼면 되는 쉬운 문제 인줄 알았으나 생각보다 시간이 오래 걸렸다. 

큰 사각형 = (가장 큰 세로 X 가장 큰 가로)
작은 사각형 = (가장 작은 세로 X 가장 작은 가로)
Result = 큰 사각형 - 작은 사각형  
이렇게 생각했으나 작은 사각형의 가로,세로값이 가장 작지 않을 수도 있는 경우를 생각하지 못해서 다른 방법을 찾았다.

방법은, 접한 (가로, 세로)의 쌍을 곱해서 모두 더하는 것  

빨간색 사각형은 3번씩, 파란색 사각형 2번씩 더해진다. (x = 빨간색, y = 파란색)
3x + 2y = 22800 (160*50 + 160*30 + 30*20 + 20*60 + 20*100 + 50*160)     // 인접한 가로*세로의 합
x + y = 160*50 = 8000 // 큰사각형 전체의 넓이
비례식을 이용하여 풀이하면 

즉, (인접한 가로*세로 값들의 합 - 가장 큰 사각형의 넓이 X 2) * K

( 22800 - 8000 * 2 ) * 7 = 47600 

※ 여기서 가장 큰 사각형의 넓이는 코드에서 인접한 사각형끼리 곱했을 때 나오는 최댓값을 갱신 하여 구하였다.


 

 

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

public class Main {
	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int sum = 0;
		int max = Integer.MIN_VALUE;
		int K = Integer.parseInt(st.nextToken());

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

		int first = Integer.parseInt(st.nextToken());
		int pre = first;

		for (int i = 1; i < 6; i++) {
			st = new StringTokenizer(br.readLine());
			st.nextToken();
			int cur = Integer.parseInt(st.nextToken());
			max = Math.max(cur * pre, max);
			sum += cur * pre;
			pre = cur;
		}
		max = Math.max(pre * first, max);
		sum += pre * first;
		System.out.println((sum - max * 2)*K);
	}
}

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

 

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수

www.acmicpc.net


동서남북으로 방향이 정해져있던 기존 BFS 와 다르게 나이트의 이동경로 8방향으로 dx,dy 배열을 초기화해주면 되는 간단한 문제이다


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, l;
	static int map[][];
	static boolean visited[][];
	static int startX, startY, endX, endY;
	static int dy[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
	static int dx[] = { -1, 1, -2, 2, -2, 2, -1, 1 };

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

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

		while (N-- != 0) {
			l = Integer.parseInt(br.readLine());

			map = new int[l][l];
			visited = new boolean[l][l];

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

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

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

			endY = Integer.parseInt(st.nextToken());
			endX = Integer.parseInt(st.nextToken());

			System.out.println(BFS(startY, startX));
		}
	}

	static int BFS(int y, int x) {
		
		if (y == endY && x == endX)
			return 0;
		
		Queue<int[]> qu = new LinkedList<int[]>();
		visited[y][x] = true;

		map[y][x] = 0;
		qu.add(new int[] { y, x });

		while (!qu.isEmpty()) {
			int[] temp = qu.poll();

			int curY = temp[0];
			int curX = temp[1];

			if (curY == endY && curX == endX)
				return map[endY][endX];

			for (int k = 0; k < 8; k++) {
				int ny = curY + dy[k];
				int nx = curX + dx[k];

				if (ny < 0 || nx < 0 || l-1 < ny || l-1 < nx)
					continue;

				if (visited[ny][nx])
					continue;

				qu.add(new int[] { ny, nx });
				map[ny][nx] = map[curY][curX] + 1;
				visited[ny][nx] = true;

			}
		}
		return -1;
	}
}

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

 

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로

www.acmicpc.net


BFS의 최단거리를 찾아낸다는 특성을 가지고 풀수 있는 문제지만 벽을 한번 부수고 가야하는 것을 고려해야 하기때문에 생각이 조금 필요한 문제였다.

1. 벽을 부수고 온 경우와 부수고 오지 않은 경우 각각 다른 방문배열에 저장 (3차원 배열)

2.  Class 내에 내부 클래스를 사용하여 필요한 변수를 저장

 

핵심 포인트는 벽을 부수고 가는 경우와 벽을 부수고가지 않는 경우를 모두 고려해야하는데 벽을 부수고 가지 않는 경우가 더 최단거리 일수도 있기때문에  3차원 배열을 사용하여 [0][ny][nx]에 벽을 부수지 않고 방문한 경우, [1][ny][nx]에는 벽을 부수고 방문한 경우, 모두 저장해줘야한다. 


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static boolean visited[][][];
	static int map[][];
	static int dy[] = { 1, 0, -1, 0 };
	static int dx[] = { 0, 1, 0, -1 };

	static class Point {
		int x, y, dis;
		boolean destroyed;

		public Point(int x, int y, int dis, boolean destroyed) {
			this.x = x;
			this.y = y;
			this.dis = dis;
			this.destroyed = destroyed;
		}
	}

	public static void main(String[] agrs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		visited = new boolean[2][N + 1][M + 1];
		map = new int[N + 1][M + 1];

		for (int i = 1; i <= N; i++) {
			String temp = br.readLine();
			for (int j = 1; j <= M; j++) {
				map[i][j] = temp.charAt(j - 1) - '0';
			}
		}

		BFS();

	}

	static void BFS() {
		Queue<Point> qu = new LinkedList<Point>();

		qu.add(new Point(1, 1, 1, false));

		visited[0][1][1] = true;

		while (!qu.isEmpty()) {

			Point curP = qu.poll();

			if (curP.y == N && curP.x == M) {
				System.out.println(curP.dis);
				return;
			}
			
			for (int i = 0; i < 4; i++) {
				int ny = curP.y + dy[i];
				int nx = curP.x + dx[i];

				if (ny <= 0 || nx <= 0 || N < ny || M < nx)
					continue;

				// 벽이 아닌 경우
				if (map[ny][nx] == 0) {
					//지금까지 벽을 부순적인 없는 경우
					if (!curP.destroyed && !visited[0][ny][nx]) {
						qu.add(new Point(nx, ny, curP.dis + 1, false));
						visited[0][ny][nx] = true;
					}
					// 벽을 부수고 온경우
					else if(curP.destroyed && !visited[1][ny][nx]) {
						qu.add(new Point(nx, ny, curP.dis + 1, true));
						visited[1][ny][nx] = true;
					}
				}
				// 벽인 경우
				else {
					// 벽을 부시고 방문한 적이 없으면
					if (!visited[1][ny][nx] && !curP.destroyed) {
						// 벽을 부시고 방문
						qu.add(new Point(nx, ny, curP.dis + 1, true));
						visited[1][ny][nx] = true;
					}
				}
			}

		}

		System.out.println(-1);

	}

}

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

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net


1차원 BFS 를 활용하여 풀수 있는 단순한 문제다.

+1, -1, *2 가 되는 경우를 각각 변수에 저장하여 Queue에 넣어주고

Map 배열에 몇초에 방문할수 있는지 저장하였다.

N = K 인 경우까지 고려하여야 하고, N,K 범위가 0도 가능하다


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, K;
	static int cnt = 0;
	static int map[] = new int[100001];

	static Queue<Integer> qu = new LinkedList<Integer>();

	public static void main(String agrs[]) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		BFS(N);
		System.out.println(map[K]-1);
	}

	static void BFS(int N) {
		qu.add(N);
		map[N] = 1;

		if (N == K)
			return;
		
		
		while (!qu.isEmpty()) {
			int cur = qu.poll();

			if (cur == K)
				break;

			int a = cur + 1;
			int b = cur - 1;
			int c = cur * 2;

			if (0 <= a && a < 100001 && map[a] == 0) {
				qu.add(a);
				map[a] = map[cur]+1;
			}

			if (0 <= b && b < 100001 && map[b] == 0) {
				qu.add(b);
				map[b] = map[cur]+1;
			}

			if (0 <= c && c < 100001 && map[c] == 0) {
				qu.add(c);
				map[c] = map[cur]+1;
			}
		}
	}
}

 

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

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,

www.acmicpc.net


7576번 문제의 3차원 배열 버전이다

푸는 방식은 동일하지만, 높이를 고려해야 하기때문에 배열을 3차원으로 선언하여 x,y 뿐만아니라 z까지 이동하는

방법으로 풀었다. static int N , M, H, 을 선언하고 int N, M, H 를 또 선언해줘서 괜한 시간 낭비를 했었다 ..


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int M, N, H;
	static int cnt = 0;
	static int map[][][];
	static int dx[] = { 1, 0, -1, 0, 0, 0 };
	static int dy[] = { 0, 1, 0, -1, 0, 0 };
	static int dz[] = { 0, 0, 0, 0, 1, -1 };
	static boolean visited[][][];
	static Queue<int[]> qu = new LinkedList<int[]>();

	public static void main(String agrs[]) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());

		map = new int[H + 1][N + 1][M + 1];

		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= N; j++) {
				st = new StringTokenizer(br.readLine());
				for (int k = 1; k <= M; k++) {
					map[i][j][k] = Integer.parseInt(st.nextToken());

					if (map[i][j][k] == 1) {
						qu.add(new int[] { i, j, k });
					}
				}
			}
		}

		BFS();

		Loop1: for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= N; j++) {
				for (int k = 1; k <= M; k++) {
					cnt = Math.max(map[i][j][k], cnt);

					if (map[i][j][k] == 0) {
						cnt = -1;
						break Loop1;
					}

				}
			}
		}
		if (cnt != -1)
			System.out.println(cnt - 1);
		else 
			System.out.println(cnt);
	
		

	}

	static void BFS() {

		while (!qu.isEmpty()) {
			int curH = qu.peek()[0];
			int curY = qu.peek()[1];
			int curX = qu.peek()[2];

			qu.poll();

			for (int i = 0; i < 6; i++) {
				int nh = curH + dz[i];
				int ny = curY + dy[i];
				int nx = curX + dx[i];

				if (nh <= 0 || ny <= 0 || nx <= 0 || nh > H || ny > N || nx > M)
					continue;

				if (map[nh][ny][nx] != 0)
					continue;

				qu.add(new int[] { nh, ny, nx });

				map[nh][ny][nx] = map[curH][curY][curX] + 1;

			}

		}
	}
}

 

+ Recent posts