문제 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 다익스트라를 각 노드 별로 수행해서 해결해야하나 했다가, 인접 매트릭스를 쓰면 될 것 같아 코드를 작성하다 실패. 인접 매트릭스를 활용한 최단거리 알고리즘이 플로이드 워셜이란걸 검색해서 알아내 이걸로 해결 #include #define MAX_DIST 1501 int items[101] = {0, }; int max_items = 0; int adj_mat[101][101]; void sol(int n, int m) { for (int i = 1; i < n + ..
전체 글
14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 벽을 하나씩 추가하고 3개가 추가되면 해당 상태에서 안전 구역을 BFS를 통해 얻고, 최대 안전 구역보다 크다면 갱신. 벽을 추가하는 과정은 재귀 함수로 구현. 벽을 추가하고 그 다음 칸부터 벽을 세워나간다. 가능한 모든 벽 추가 경우의 수를 검사할 수 있다. 최대 안전 구역을 얻는 함수 수행 시, 벽은 모두 방문한 것으로 처리했다. 방문하지 않은 바이러스가 있는 곳에서 BFS를 통해 감염되는 구역을 모두 방문 처리 후, 방문하지 않은 곳의 수를 세어주면 안전 구역 크기를 알..
12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 처음 문제를 읽고 BFS를 떠올리긴 했는데, 뭔가 방문을 처리하는 배열을 boolean으로 만든다면 모든 경우의 수를 찾을 수 없다고 생각했다. '조건문으로만 처리해서 할 수 있지 않을까?'라고 생각했다가 각 지점에 도달하는 최소 시간을 기록하기로 했다. 고려한 조건들 현재까지 이동한 시간이 '목적지(k)까지의 최소시간'보다 크면 continue '각 지점에 도달하는 최소 시간'보다 큰 시간에 도달하면 그다음은 고려하지 않고 ..