본문 바로가기

bfs10

[JAVA] 백준 - 캐슬 디펜스 17135 (테케 다 맞는데 틀린다면?) www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 자꾸 틀린다면 꼭 점검해야할 상황을 소개한다. (본인 경험) 1. 궁수 3명을 배치하는 모든 경우를 구했는가? - 문제에서 N+1 번째 칸에 궁수 3명을 배치한다고 하였다. 한 칸에 한명만 올 수 있다. 따라서 M개의 자리에서 3개를 선택하는 모든 경우의수를 구해야한다. Combination 로직을 DFS로 구현해주면 된다. 여기에서 M = 5 일때 3개의 자리를 선택하는 경우의 수는 5C3 이므로 10가지가 나와야한다... 2021. 3. 4.
[JAVA] 백준 7562 - 나이트의 이동 ( BFS) www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net -이동할 방향 코드 작성 static int[] dx = {-1,-2,-2,-1,1,2,2,1}; static int[] dy = {-2,-1,1,2,2,1,-1,-2}; 10시 방향부터 시계방향으로 8가지 위치를 지정한 것이다. 예를 들어, 기존의 위치가 (x,y) = (10,10) 이라고 가정하자. ( x + dx[0] , y + dy[0] ) = 10시방향 좌표 ( x + dx[1] , y + dy[1] ).. 2021. 2. 18.
[JAVA] 백준 2583 - 영역구하기 ( BFS + 구현 ) www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net - 사각형 칠하기 위와 같이 m=5 이고 n=7인 배열에서 왼쪽 아래 좌표(0,2) 와 오른쪽 위 좌표(4,4) 를 가지고 사각형에 해당되는 부분은 어떻게 체크 할것인가? 의 전체 큰 배열의 이름을 arr 라고 하자. (0,2) 와 (4,4)가 주어졌을 때 결과적으로 체크 되는 부분은 다음과 같다. arr[1][0] , arr[1][1] , arr[1][2] , arr[1][3] arr[2].. 2021. 2. 15.
[JAVA] 백준 - 2548 키순서 ( 플루이드 외샬 or BFS) www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 플루이드 외샬 알고리즘을 적용하면 빠르게 풀 수 있는데 나는 쓰지 않았다. BFS 를 쓰면 더 빠를 거라고 생각했기 때문이다. 실제로 더 빨라서 전체 백준 차트에서 2등했다. (물론 메모리를 좀더 쓰긴 했지만..) (2020.02.13 기준) BFS 풀이법 - 1번 정점에서 BFS를 시작하여 1번보다 큰 정점을 체크한다. 여기서는 2,4,5,6번이 체크된다. - 2번 정점에서 BFS를 시작하여 1번보다 큰 정점을.. 2021. 2. 13.
[JAVA] 백준 - 4연산 14395( BFS) www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 처음 숫자가 s 라고 할때 다음 숫자는 = s + s || s - s || s * s || s / s 이다. '-' 와 '/' 는 반드시 0 과 1 이된다. 사실 t 가 0 이면 '-' 를 반환하면 되고 t가 1이면 '/'를 반환하면 된다. 그렇다고 해서 '/' 와 '-' 를 연산에서 제거하면 안된다. 모든 경우의 수를 살펴야 한다. 예를 들어 s = 10 / t = 8 이라면 (((10 / 10) + .. 2020. 10. 16.
[JAVA] 백준 - 소수 경로 1963 ( BFS + 에라토스테네스의 체) www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 1000 에서 9999까지 미리 모든 소수를 체크해놓는 것이 좋다. 소수를 체크하는 알고리즘은 에라토스테네스의 체를 사용하여 소수를 체크한다. public static void makePrimeNumber(){ for(int i=2;i 2020. 10. 16.
[JAVA] 백준 - DSLR 9019 ( BFS) www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 � www.acmicpc.net 클래스 Pair 를 계속 생성해서 그런지 모르겠는데 메모리 엄청 쓴다.. 쓰지 않으면 더 빠르게 구동 되지만 직관적으로 이해하고 문제 풀이가 빨라서 Pair 클래스를 만들어서 쓰고 있다. # 문제의 관건인 D S L R 을 구현하기 //D nx = (x*2)%10000; //S nx = x==0?9999:x-1; //L nx = (x%1000)*10 + (x/1000); //R nx = (x/1.. 2020. 10. 8.
[JAVA] 메모리 사용량과 시간을 줄이는 간단한 아이디어 문제는 백준 2573번 문제로 진행했다. https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 1. 문제 풀이 1) 2차원 배월의 모든 원소가 0인가? 그렇다면 6)으로 간다. 그게 아니라 하나라도 0보다 큰 수가 있다면 2)번으로간다. 2) answer 를 1증가 시킨다. 3) 2차원 배열을 1년이 지난 배열로 만든다. 4) bfs를 이용해 영역의 수를 카운트하고 2이상이면 ok에 표시하고 6)번으로 간다. 5) 2)반복한다. 6) ok가.. 2020. 8. 20.
[JAVA] 토마토 (백준 7569) 이 문제는 2차원이 아니라 3차원으로 bfs푸는 것이다. 또한 익기 시작하는 지점이 정해진 것도 아니며 여러개가 있을 수도 있고 없을 수도 있다. 관건은 모든 토마토가 익었는지 확인하는 것과 모두 익었다면 며칠이 걸리는지 구하는 것이 핵심이다. 본인이 접근한 방법대로 2층짜리 3x3 토마토상자가 있다고 가정하고 풀어보는 예시를 보자. 예) (z,x,y) 에서 z 는 높이이며 , x 는 가로, y는 세로다. x,y,z 모두 0부터 시작한다. 시작전 ( 0초 ) 큐에 남은 좌표 : (0,1,1) 1층 0 0 0 0 1 0 0 0 0 2층 0 0 0 0 0 0 0 0 0 1초후 큐에 남은 좌표: (0,0,1) , (0,1,0), (0,2,1) , (0,1,2) 1층 0 2 0 2 1 2 0 2 0 2층 0 0.. 2020. 8. 15.

티스토리툴바