24513번: 좀비 바이러스 여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$ www.acmicpc.net 풀이 방법 bfs가 한턴씩 지날 때마다 몇번째 방문인지 저장하기 위해 copy 배열을 만들었다. 처음은 첫번째 방문으로 가정해 1을 넣어주었다. 이렇게 턴을 돌 때마다 copy에 현재 몇번째 턴인지 저장해두었다. 만약 map[nx][ny]를 방문했을 때 copy[nx][ny]에 저장된 값과 현재 턴수가 같고, map[nx][ny]와 map[x][y]이 다르면 침범이 일어났다는 뜻이므로 map[nx][ny] 값을 3으로 바꿔주었다. 자바 코드 import..

15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 15961과 2531은 범위만 다를 뿐, 같은 문제 풀이 방법 예제 입력1을 기준으로 설명하려고 한다. 이를 배열로 옮겨보자. 초밥을 k..

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 방법 문제에 주어진 예제1번을 그려보면 이렇게 된다. 편하게 생각할려고 세로축을 밑에서부터 1로 생각했다. 석순(인덱스가 홀수(odd)), 종유석(인덱스가 짝수(even))를 나누어서 계산했다. 생각해보면 높이가 1일 때, 1과 같거나 큰수에서 부딪힌다는 것을 알 수 있다. 따라서 만약 내가 높이 1일때 몇개의 석순에 부딪히는지 알고 싶다면, 1보다 크거나 같은 석순의 개수를 세어주면 된다. 그..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 JUNGOL www.jungol.co.kr 풀이 방법 N이 작기 때문에 모든 방법을 다 해보는 완전탐색이 가능하다. 따라서 DFS를 이용해 모든 경로를 탐색하며 최소 거리를 구했다. 시간을 줄이기 위해 구한 최소거리보다 지금 가고있는 거리가 더 크다면, 그 방법은 구하지 않았다. (if(cnt+map[r][i]>=min) continue;) 또한, 마지막으로 방문한 곳 -> 1로 가는 거리를 구할 때 그래프가 연결되어있지 않다면 거리를 구하지 않아야 한다. 자바 코드 import java.io.BufferedReader; import java.io.IOException; import ..