DFS, BFS 둘 다 풀 수 있는 문제 (링크 : https://www.acmicpc.net/problem/2234) 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트마스킹으로 BFS의 방향을 나타내는 방법이 힌트에 나와있었지만 비트마스킹이 뭔지 몰랐기에 그냥 하던대로 구현을 하려고 했지만,, 메모리 초과의 벽을 넘지 못했다.. ◆ 기존 구현 방법 각 좌표에 있는 번호를 when으로 분기문으로 8,4,2,1 숫자를 순서대로 0이 될때 까지 빼줌으로써 방향을 구하는 방식을 사용함 근데 이 과정에서 변..

지도의 영역 개수와 영역의 너비를 구하는 문제 (링크 : https://www.acmicpc.net/problem/2583) 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 소스코드(BFS) import java.io.BufferedReader import java.io.FileInputStream import java.io.InputStreamReader import java.util.LinkedList import java.util.Queue import java.util.StringT..

지도의 영역 개수를 구하는 문제 (BFS , DFS 둘 다 풀이가 가능) (링크 : https://www.acmicpc.net/problem/10026) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 소스코드(DFS) import java.io.BufferedReader import java.io.FileInputStream import java.io.InputStreamReader private val MY = arrayOf(0,0,1,-1) //좌 ,우 ,위 ,아래 private val MX = a..

(링크 : https://www.acmicpc.net/problem/2606) 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 소스코드(BFS) import java.io.BufferedReader import java.io.FileInputStream import java.io.InputStreamReader import java.util.LinkedList import java.util.Queue private var N = 0 //컴퓨터 수 private var M = 0 //관계 수 private latei..

(링크 : https://www.acmicpc.net/problem/2667) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 소스코드(BFS) import java.io.BufferedReader import java.io.FileInputStream import java.io.InputStreamReader import java.util.LinkedList import java.util.Queue private val MY = arrayOf(0,0,1,-1) //좌 ,우 ,위 ,아래 private val M..

3차원배열에서 BFS를 사용해서 풀었던 문제 (링크 : https://www.acmicpc.net/problem/7569) 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 소스코드 import java.io.BufferedReader import java.io.FileInputStream import java.io.InputStreamReader import java.util.* private var M = 0 //가로 (2 이상 100이하) private var N = 0 //세로 (..

처음에는 따로 Point라고 Data class를 만들어서 조건을 만족하는 자리를 만나면 해당 객체에 좌표를 보관하는 식으로 문제를 풀었엇는데 계속해서 메모리 초과가 나왔다. 메모리를 어떻게하면 줄일 수 있을까 하고 계속해서 고민해보고 허탕치다가 데이터클래스를 안쓰고 colum값만 저장하는 방식으로 푸니까 풀렸다. 교훈 : DFS풀때 data class(객체) 사용하면 메모리를 생각보다 많이 잡아먹으니 감안하고 코드를 짜자! (data class 뿐만아니라 Pair 사용해도 메모리를 많이 먹으니 메모리 커트라인이 넉넉하지 않다면 그냥 객체 사용을 지양하는게 좋을듯 하다.) (링크 : https://www.acmicpc.net/problem/9663) 9663번: N-Queen N-Queen 문제는 크기가..

그냥 시간 복잡도 계산해서 좌우 Pivot잡아서 풀었었는데 이진 탐색 으로도 풀 수 있는 문제였다. 아래 이진탐색 코드도 첨부 링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net #Pivot 풀이 import java.io.BufferedReader import java.io.FileInputStream import java.io.InputStreamReader fun main() { val..

이런 유형도 DFS ,BFS로 풀 수 있구나 깨달았던 문제 다른 블로그 들을 참고하면서 DP와 BFS에 대해서 좀 더 깊게 깨달았구나 싶다. 링크 : https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 해당 문제를 그리디로 머리 꽁꽁싸매고 열심히 풀어보았으나 1488 2 일 때, 8841 이 나오겠지만, 4188 2 일 때, 8814가 나옴으로 아래 그리디 방식으로는 풀 수 없다.. (다른 블로그도 그리디는 다 실패하신듯 하다..) 그 후 BFS와 DFS로 구현할 수 있다는 걸 알고 아래 블로그를 참고하고 풀었다. (..