힘들면 힘을내자!

[백준 14503] 로봇 청소기(Java) https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 해결 방법 1트 문제를 읽고 작동이 멈출때 까지 loop를 사용하면 되어서 BFS로 접근해서 해결했습니다. 저는 방향을 돌리는 것이 수식으로 생각이 나지 않아서 조건문을 모두 만들어서 해결했습니다. 조건대로 구현을 했는데! 틀렸습니다. ㅠ0ㅠ 2트 디버깅을 통해 틀린 이유는 바로 청소한 부분을 다시 지나갈..

[백준 7569] 토마토(Java) 7569번: 토마토 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 해결 방법 1트 문제에서 최소 날짜를 구하라고 해서 바로 BFS를 생각했습니다. 문제를 해결하기 위해서는 3차원 배열에 대한 이해가 있어야 합니다. 그리고 익은 토마토의 상, 하, 좌, 우, 윗칸, 아랫칸에 위치한 토마토는 익습니다. 그림으로 표현하면 아래와 같습니다. 이를 코드로 표현하면 다음과 같습니다. // 3차원 배열 int[][][] box = new int[z][x][y];..

[백준 2644] 촌수계산(Java) 2644번: 촌수계산 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 해결 방법 1트 부모자식간에는 1촌이라는 사실을 이용하여 DFS를 사용하여 문제에서 주어진 사람1(노드1)에서 시작해서 사람2(노드2)에 도달할때 깊이(depth)를 출력하면 됩니다. 촌수가 없으면(노드가 연결 안되있으면) -1을 출력하면 됩니다. 풀이 public class Quiz2644 { static int n; static int member1; static int membe..

[백준 5014] 스타트링크(Java) 5014번 스타트링크 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 해결 방법 1트 처음에 DFS를 이용해서 문제를 해결하려고 했습니다. G층에 도착했을 때 깊이를 계산하면 되기 때문이죠! // 시간초과... private static void dfs(int depth, int now) { if(now > f || now f || poll.getNode()

[백준 1987] 알파벳(Java) 1987번: 알파벳 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 해결 방법 1트 DFS를 사용하여 모든 경로를 탐색하고 경로의 길이가 가장 긴 것을 출력하면 되는 문제 입니다. 풀이 public class Quiz1987 { static int r; static int c; // 상, 하, 좌, 우 static int[] ud = {1, -1, 0, 0}; static int[] lr = {0, 0, 1, -1}; static Character[][] map; s..

[백준 2468] 안전 영역(Java) https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 해결 방법 1트 문제를 보고 DFS또는 BFS로 해결하면 좋을 거라고 판단했습니다. 저는 DFS를 사용했습니다. 시작 지점에서 DFS가 종료될때 마다 count를 증가시키면 된다고 생각했습니다.^^ 그런데…. 틀렸습니다. 2트 문제를 다시 읽어보니 최대 안전 영역을 구하라고 했습니다. 저는 n을 기준으로 안전영역을 구하는 것인지 알았습니다..😭 따라서 지역에서 최대..

[백준 1260] DFS와 BFS(Java) 1260번: DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 해결 방법 1트 처음에 엄청 쉽다고 생각해서 기계적으로 DFS, BFS를 구현했습니다. 그런데 틀렸습니다….😭 이유가 뭘까… 생각하고 다시 문제를 읽어보았습니다. 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 문제의 조건이 있었습니다.. 2트 정점 번호가 작은 것부터 방문하려면 어떻게 해야할까… 고민한 결과 DFS는 모든 노드를 탐색..

[백준 1967] 트리의 지름(Java) https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 해결 방법 결론 트리에서 노드 간의 최대 거리를 구할 때는 DFS를 이용한다. 루트 노드에서 가장 먼 노드를 찾는다. 아무 노드나 해도 상관 없음 찾은 노드에서 가장 먼 노드까지의 거리를 구한다. 1트 처음에는 엄청 쉽다고 생각했습니다. 😄 아 루트 노드를 중심으로 거리가 가장 먼 노드를 찾으면 되는구나! 라고 생각하여 계산해 보니 43..

[백준 16953] A → B(Java) 16953번: A → B 해결 방법 DFS또는 BFS 를 사용해서 해결하면 됩니다.👍 연산의 종류에 따라서 자료 구조에 데이터를 삽입하고 꺼내는 것을 목표값을 찾을 때 까지 반복 합니다. 2023.03.19 - [0 + 알고리즘(Algorithm)] - [알고리즘] 너비 우선 탐색(BFS: Breadth First Search, 백준 2178, 1697, 12851, 1012 -Java) [알고리즘] 너비 우선 탐색(BFS: Breadth First Search, 백준 2178, 1697, 12851, 1012 -Java) [알고리즘] 너비 우선 탐색(BFS: Breadth First Search, 백준 2178, 1697, 12851, 1012 -Java) 알고..

[백준 1504] 특정한 최단 경로(Java) 1504번: 특정한 최단 경로 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 해결 방법 처음에 u, v만 거쳐가면 된다라고 생각해서, 단순하게 start -> u -> v -> end이렇게 가는 최단경로를 구하면 되겠네! 라고 생각했습니다.ㅎㅎ 하지만, u와 v를 거쳐 가라고만 했지 u -> v 이런 순서로 가라고 한적은 없었습니다.😭 따라서 u -> v, v -> u 인 2가지 경우를 고려해야 합니다. 저는 다익스트..