힘들면 힘을내자!

[백준 9205] 맥주 마시면서 걸어가기(Java) 백준 9205: 맥주마시 면서 걸어가기 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 해결 방법 1트 문제를 읽고 DFS를 이용하여 해결하려고 했습니다. 하지만, 구현해 보니 페스티벌에 갈수 있는지 없는지 판별하기가 어려웠습니다. 경로 하나만 맥주를 다 못마시면 sad를 출력했기 때문입니다. ㅠㅠ 2트 BFS를 사용해보았습니다. 그런데 x, y 좌표가 음수의 값을 갖을 수도 있습니다.. 그래서 문제를 해결하지 못했습니다. 3트 결국 다른 사람의 풀이를..

[백준 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..

[알고리즘] 플로이드-워셜(백준 11404, 1389, 11403 -Java) 알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇 본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다. 물론 혼자하면 작심삼일이 될거 같아 무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의 강의 커리큘럼에 맞춰 공부해보자!! [무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의 IT기업 코딩테스트 대비를 위한 [자료구조 및 알고리즘 핵심이론 & 관련 실전 문제 풀이 강의] 입니다. - JAVA 편 -, - 강의 소개 | 인프런 www.inflearn.com 플로이드-워셜 플로이드-워셜 알고리즘은 방향 그래프에서 최단 거리를 구하는 알고리즘 입니다..