[JAVA] 백준 - 데스나이트 (BFS)
www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 가장 기본적인 로직만 있는 문제. 상하좌우가 아니라 이동할 수 있는 다음 장소가 6군데라는점만 조심하면 된다. 또한 한번 방문한 곳을 또 방문하여 최단거리를 갱신하는 일은 없으므로 2차원 배열로 방문 체크를 해도된다. import java.util.LinkedList; import java.util.*; class Main{ stat..
2020. 10. 8.
[JAVA] 백준 구슬탈출 2 - 13460 ( DFS & 구현)
www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구현 + dfs 문제 1. 빨간 구슬과 파란 구슬은 동시에 같은 위치에 있을 수 없다.(핵심구현) 구현의 첫번째 난관이다. 아래처럼 방향을 정하고 int[] dx = {-1,1,0,0}; int[] dy = {0,0,-1,1}; 기존 위치가 [x,y] 라면 다음 위치는 [ x + dx[i], y + dy[i] ] 이다. (이때 i는 0부터 3까지 중 하나의 숫자..
2020. 10. 1.
[JAVA] 백준 -부분 수열의 합 14225
www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 � www.acmicpc.net 부분 수열이 처음엔 연속된 수의 나열인 줄 알고 풀었다가 아니였다. 원래 수열이 [1,4,3,2,3,1] 와 같이 있다면 [1], [1,3,2],[1,4,3],... 처럼 1개 이상의 원래의 순서를 유지한 수열을 부분 수열이라고 한다. 이러한 정의를 문제에 알려주면 좋았다만.. 여튼 문제는 어렵지 않으나 문제는 방문 체크이다. 방문 체크를 ..
2020. 9. 22.
