최's 먹공로그
1. 예전에 BFS로 풀었던 적이 있어서 DFS로 풀어보려고 했지만 흠 최단거리라서 BFS로 풀어야 되는걸까?? 2. DFS돌면서 visit 체크 해주고 인접한 4방향 보면서 N M까지 찾도록 함 3. map에 cnt 값 업데이트 해주면서 진행하고 마지막에 map[N][M]에 있는 값 출력 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2178_미로탐색 { static int N; static int M; static int[][] map; static int[][] visit; public sta..
1. 두개의 노드가 연결되어 있다는 어찌 표현할지 -> 2차원 배열에 연결되어 있는 노드는 1로 표현 1,2가 연결인 경우 0 1 0 0 1 0 0 0 이런식으로 2. visit은 방문한 노드만 체크 -> 1차원 배열로 노드만 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 BOJ1260_BFSDFS { static int[] visit; static int[][] map; static int N, M; publ..
1. 지민이가 만들고 싶은 상태의 체스판과 비교해서 cnt 비교하여 최종 cnt 갱신 2. 검사할 때 +8 할 경우 map을 넘어가지 않는지 검사 필수 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ1018_체스판 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new ..
문제정리 https://choish313.tistory.com/121 JAVA 버젼 확인 C++ 익숙해 지기 위한 다시 풀기 소스코드 #include #include #include #include using namespace std; char board[13][7]; char board2[13][7]; int down[7]; bool vis[13][7]; vector v; queue q; queue pq; void input() { ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL); for (int i = 0; i > board[i][j]; board2[i][j]..
* heap에 대한 이해 * 배열, c++을 이용하여 heap을 구현 * 완전 이진 트리의 일종으로 우선순위 큐를 구현하기 위해 만들어진 자료구조 * 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아낼 수 있다. * 힙은 반정렬 상태를 유지 -. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도(혹은 그 반대) * 힙 트리에서는 중복된 값을 허용한다. * 최대 힙, 최소 힙 -. 부모 노드의 키 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리 key(부모노드) >= key(자식노드) -. 최소 힙은 그 반대 * 도식화 * 힙을 저장하는 표준적인 자료구조는 배열 이다. * 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. * 특정 위치의 노드 번호는 새로운 노드..
https://www.acmicpc.net/problem/11559 문제정리1. 룰(1) 뿌요는 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.(2) 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색뿌요들이 한꺼번에 없어진다.(3) 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 아래로 떨어지게 된다.(4) 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.(5) 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.2. 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산3. map[..
https://www.acmicpc.net/problem/17136 문제정리1. 색종이의 크기가 1*1 , 2*2 , 3*3 , 4*4 , 5*5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.2. 색종이를 크기가 10 * 10인 종이 위에 붙이려고 한다. 1이 적힌 칸은 모두 색종이로 덮어져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다.3. 종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.4. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다. 문제issue1. 재귀를 이용한다. 해결흐름1. map을 입력 받을 때 1의 위치를 list에 저장한다.2. 재귀(1..