갱스터하우스

➡️문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/43162 💡아이디어BFS, DFS, 그래프탐색! 사실 알고리즘고득점 kit의 깊이/너비 우선 탐색(DFS/BFS)에 있는 문제여서문제의 유형이 무엇인지는 이미 알고 있었다 그래도 문제에서"컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다." 라는 부분을 읽고, 타고타고가 가능하네? -> 그럼 1부터 N까지 각 정점을 탐색하면서 하나의 정점에서 방문할 수 있는 노드를 다 방문하자-> ..

➡️문제 링크https://www.acmicpc.net/problem/14502 💡아이디어조합과 bfs ✏️문제 풀이1. 조합, bfs - 성공 (1) 빈 칸에서 바이러스를 막아줄 벽 3개를 뽑는다.(조합)(2) (1) 에서 추출한 벽을 바탕으로 바이러스 확산한다.(bfs)(3) 확산 후, 남아있는 빈칸을 비교하면 최대 영역의 수 갱신하기 처음에는 확산 후, 남아있는 빈칸을 비교할 때 매번 이중 for문을 돌면서 빈칸을 세야하나 고민했다.그러다 빈칸의 총 수를 먼저 구해놓고, 확산할때마다 한 칸씩 감소하는 게 더 효율적이라고 생각했다. import java.io.*;import java.util.*;/* * 1. 3개의 벽 조합으로 구하기 * 2. 1의 결과로 바이러스 확산 * 3. 이 후 안전영..

➡️문제 링크https://www.acmicpc.net/problem/16953 💡아이디어 필요한 연산의 최솟값 그래프 탐색이다! 싶었다뭔가 예전에 풀었던 숨바꼭질 느낌도 나고 ✏️문제 풀이1. BFS - 성공 나온 조건 그대로 곱하고, 오른쪽 자리에 1을 추가해 범위내, 방문 여부 확인하고 BFS 돌렸다그리고 poll() 할 때, 해당 수가 B라면 BFS 종료 후 정답 출력import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub BufferedReader br = new Buffered..

➡️문제 링크https://www.acmicpc.net/problem/11725 💡아이디어BFS 돌리기처음에는 어떤 자료구조를 이용해야하나 감이 잘 안 잡혀서 시간이 조금 걸렸다다시 생각해보면 문제 이름에 "트리"가 들어가 있어 "결국 트리를 직접 구축해야되는 문제 아니야?"라는 생각이 자꾸 들어조금 헤맨 것 같다. ✏️문제 풀이1. BFS, 단방향 그래프 - 오답1은 무조건 루트가 확정이니, 입력 받을 때부터 (작은 값, 큰값) 이렇게 정렬을 해 작은 값은 부모, 큰 값은 자식 설정을 할까 고민을 하다 항상 보장한다는 경우가 없어 패스그러다 1은 루트 확정이니, A 1 이렇게 오는 경우를 제외하고는 첫 번째 값을 부모, 두 번째값을 자식으로 추정해 리스트에 저장을 하고 BFS를 1부터 N까지 돌려..

➡️문제 링크https://www.acmicpc.net/problem/16928 💡아이디 플레이어는 주사위를 굴려 나온 수만큼 이동 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다 -> 그래프 탐색이다 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값 -> 최솟값이니까 bfs 아닐까? 이 과정을 거쳐 이 문제는 bfs로 풀어야겠다고 생각했다 처음에는 2차원 배열을 만들어 접근하려고 했다.그런데 풀다보니 꼭! 2차워 배열로, 해당 숫자의 위치를 정확하게 알아야 이 문제를 풀 수 있는 걸까? 이렇게 접근하는 게 이 문제의 의도일까? 이런 생각이 들어 풀다가 우선 다 지웠다.문제의 예제에서는 단순하게 숫자만 주는 것을 보며 이 문..

➡️문제 링크https://www.acmicpc.net/problem/10026 💡아이디어그래프 탐색주어진 map을 BFS 돌리면서 구역이 몇개 나오나 보면 된다.이 문제의 포인트는 일반버전과 적록색약 버전을 어떻게 나누어서 풀지가 아닐까 싶다.처음에는 두 가지 버전 각각의 map을 저장할까 싶었지만, 갑자기 toCharArray()를 써보고 싶어서bfs를 두 가지 버전으로 돌렸다.다 풀고 나니 뭔가 아쉬워서 bfs 탐색은 하나의 메소드만, 대신 map 정보를 두 가지 버전으로 나누어 푸는 코드도 풀어봤다. ✏️문제 풀이1. BFS(map 1개만) - 성공 map 정보는 1개만, bfs 로직은 2개(일반버전/적록색약 버전)import java.io.*;import java.util.*;public ..

➡️문제 링크https://www.acmicpc.net/problem/7569 💡아이디어bfs 돌리기저번에 풀었던 7576 토마토 문제랑 같은 문제지만, 이번에는 3차원 상에서 토마토를 익혀야 한다 [Java] 백준 7576.토마토➡️문제 링크https://www.acmicpc.net/problem/7576 💡아이디어보자마자 bfs 문제라고 판단했다 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을imrud.tistory.com ✏️문제 풀이1. bfs - 성공import java.io.*;import java.util.*;public class Main { static int N, M, H; static int [][][] map; stati..

➡️문제 링크https://www.acmicpc.net/problem/7576 💡아이디어보자마자 bfs 문제라고 판단했다 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. -> 사방탐색 그 최소 일수를 알고 싶어 한다. -> bfs 결론은, 익은 토마토의 bfs 돌려서 인접한 토마토 익히고 판단하기! ✏️문제 풀이1. bfs - 성공 완탐을 돌려서 1일때마다 bfs를 돌릴 수도 있고 토마토를 다 익히고 완탐해서 0이 남아있는지 확인할 수 도 있고여러가지로 구현할 수 있다나는1. 익은 토마토의 위치를 que에 저장하기2. 익지 않은 토마토의 개수 count하기3. 1을 이용해서 바로 bfs 탐색하기4. bfs 탐색하며 토마토를 하나 ..

➡️문제 링크https://www.acmicpc.net/problem/11403 💡아이디어한 번에 문제가 이해되지 않았다뭔 말이야..? 싶어 다시 차근차근 읽어보니인접그래프를 인접행렬로 표현해 (하나의 정점 -> 모든 정점 )*n 되는지를 묻는 문제였다 ✏️문제 풀이1. bfs - 성공 그래프 탐색인데 어떻게 해야할까 고민하다 일단, 0 ~ N-1 까지 행을 기준으로 돌면서 bfs를 진행했다.여기서 포인트는 양방향 그래프가 아니다 보니까, 정점을 거치면서 도달할 수 있는지 여부를 판단하는게 중요했다.import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOExceptio..

➡️문제 링크https://www.acmicpc.net/problem/17141 아이디어문제를 보자마자 조합 + bfs가 생각났다. 야호~ 문제 풀이1. 2번 위치(바이러스 퍼뜨릴 수 있는 위치)를 M개 조합한다.(이때, 2번 위치의 총개수보다 M개가 더 많을 경우, 현재 위치로 바이러스를 바로 확산한다.즉, 조합 과정을 거치지 않음!)2. 1번의 조합으로 바이러스를 퍼뜨린다.3. 바이러스를 퍼뜨린 후, map을 전체 탐색하며 벽을 제외한 모든 영역에 바이러스가 확산됐는지 확인한다.4. 3의 과정을 통과했을 경우, 1번에 최대시간값을 현재 최소 시간값과 비교하여 갱신한다. import java.io.*;import java.util.*;public class Main { static int N, M;..