내가보려고만든 메자노트

(정점=노드 같은 뜻! 혼용해서 사용할 시 혼동 방지!) 그래프에서 각 정점끼리 사이의 최단 거리를 구하는 알고리즘 방법은 여러 가지가 있다. 문제에 따라 효율적인 방법이 다르므로 잘 선택해서 사용해야 한다. 문제의 종류 하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 각 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 응용으로 한 중간 정점을 거쳐서 가는 최단경로 등 다양한 문제의 종류에 적용하여 사용할 수 있다. 알고리즘 종류 하나의 정점에서 다른 모든 정점까지 최단경로를 구하는 문제 -간선의 가중치가 모두 같은 그래프일 경우 BFS -간선의 가중치가 각각 다른 그래프일 경우 다익스트라 벨만-포드 → 음수 가중치..

문제보러가기 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 이 문제는 기존 bfs처럼 영역을 나눠서 영역의 개수, 영역의 최대 넓이 , 벽을 하나 제거한 후의 영역의 최대 넓이를 구하는 여러 문제가 합쳐져 있는 복합적인(?) 문제였다. 여기서 까다롭게 봐야 할 점은 벽을 제시할 때 0~15의 값으로 주어지며 이를 bit로 변환하여 사용해야 한다는 점이었다. 문제풀이 - bfs로 구한 영역을 증가하는 groupCnt를 키값으로 묶어 아래 그림처럼 group [][]에 저장해준다. -bfs로 영역을 구할 ..

문제보러가기 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이문제는 전형적인 탐색 문제로 연결된 영역이 몇 개가 있는지 구하는 문제였다. 다른 점이라면 위, 아래, 오른쪽, 왼쪽이 아닌 대각선 포함 8방향으로 탐색해야 한다는 점. 문제풀이 -map [][]에 입력받은 값을 저장해준다. -map을 이중 for문으로 탐색하면서 1일 경우(섬일 경우) 그리고 방문하지 않았을 경우에 bfs()를 수행한다. -4방향이 아닌 대각선 포함 8방향으로 체크해주면서 연결된 섬의 개수를 체크한다. 사실 이문제는 "메모리..

문제보러가기 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이문제는 탐색 문제로 bfs를 이용해 풀었다. 100까지 갈 때 최소한의 주사위를 던져서 가는 것이므로 bfs라고 분류한 것을 보지 않아도 bfs임을 유추할 수 있다. 일반 bfs와 다르게 동서남북 방향이 아닌 1~6까지의 숫자로 이동하는 부분만 잘 처리해주면 문제없이 풀 수 있다. +참고로 메모리 초과가 뜬다면 visited [][]로 체크해주는 부분이 빠졌는지 확인해보자..!! 사실 내가 메모리 초과가..

문제 보러 가기 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 음... 문제가 어려웠던 건 아니겠지... 나는 어려웠다. 우선 이문제는 dfs도 bfs도 가능하다! 다른 분들의 풀이를 보니 어떤 분은 dfs와 bfs를 함께 사용하기도 했다. 나는 bfs를 사용했다 고려사항 -인구이동의 조건 : 각 인접한 나라가 L = n) { continue; } int diff = Math.abs(map[tmp.x][tmp.y] - map[sx][sy]); if ((diff r) ..