룰루랄라 알고리즘

반년만에 문제를 풀기 때문에 근본문제인 DFS를 다시 한번 풀어보자 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 너무 오랜만에 풀어서 기억이 안났다. 특히 2차원 배열로 행렬 만들 때 가로 세로가 너무 헷갈린다. 행렬에서 상하좌우로 움직여 구역을 나누는건 DFS로 풀자. 아직도 헷갈리는데 X:가로, Y:세로 일 때 int [X][Y] 이렇게 선언해야 할 듯. matrix = new int [M+1][N+1]로 선언한 것은 사실 M, N으로 해도 되지만 ..

문제를 푼 시간의 9/10을 문제를 잘못 이해하고 풀었다. 이러한 좌표 DFS 문제를 좋아하는데 오랜만에 풀어서 감을 잃어서 고생했다. 이 문제의 핵심은 치즈를 기준으로 DFS를 돌리는 것이 아니라 공기를 기준으로 DFS를 돌리는 것이다. 또한 뒤통수를 한 대 맞은듯한 기분이든 fake가 있었는데 좌표의 가장자리 부분에는 치즈가 놓여있지 않는다는 부분이다. 이러한 문장의 의미는 좌표의 (0,0)이 무조건 공기라는 것이다. 예전 c로쓴 자료구조를 공부할 때 미로 찾기 알고리즘을 배웠었는데 해당 문제에서는 일부러 가장자리 좌표, 즉 좌표를 2개씩 늘려서 문제를 풀었다. 하지만 이 문제는 그러한 수고를 덜어주도록 처음부터 좌표에 제한된 부분을 포함시켜 주었다. https://www.acmicpc.net/pro..

자바로 처음 풀어본 알고리즘 문제. 알고리즘을 너무 오랜만에 풀어봐서 감을 익히려고 알고리즘 근본 문제인 dfs, bfs를 풀어봤다. 자바는 그동안 사용했던 파이썬과 다른 점이 매우 많은 것 같다. 파이썬이 얼마나 선녀였던지 알 수 있었지만 학기 내내 사용하던 로우레벨 언어 C와 비교하면 자바 또한 선녀였다. C를 사용했던 덕분에 queue와 linkedlist, sort를 직접 구현하지 않고 라이브러리를 이용할 수 있다는 것이 얼마나 편한 것인지 알았다. https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의..

그래프의 순환을 구해서 나머지 트리에서 순환그래프까지의 거리 구하기

가중치가 없는 그래프에서 다중 시작점에서부터 모든 칸까지의 최단 거리를 구하는 문제 1. 시작점을 queue에 넣어서 너비 우선 색인 BFS를 이용해 다중 시작점에서 가까운 지점부터 날짜를 업데이트하기 시작함. 2. 이중 for문으로 graph에 0이 있다면 -1을 출력하고 그렇지 않다면 최댓값을 출력함