https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 1번 노드에서부터 각 노드까지의 최단 거리를 구해야 하므로, BFS를 활용하자 그래프를 탐색하는 방법은 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있다. 이중 최단 거리를 구하는 데는 BFS를 사용한다. 사실 각 노드를 연결하는 간선의 비용을 모두 1로 둔 채 최소 비용을 구하는 다익스트라 알고리즘을 사용할 수도 있지만, 굳이 2차원 배열인 다익스트라를 사용하지 않아도 된다...
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 1. 풀이 모든 국가를 방문하면서 너비 우선 탐색(bfs)로 연합을 확인하자 N x N 크기의 땅에는 1개 이상의 연합이 존재할 수 있다. 즉, 위 그림처럼 그래프가 여러 개 존재할 수 있다는 것이다. 따라서 땅을 한 칸, 한 칸 방문해서 해당 국가가 이루는 연합 정보를 알아내야 한다. 이때 어떠한 연합에 포함된 국가는, 이전 bfs 과정에서 방문했었다는 의미이다. 따라서 재방문을 ..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 접근 방식 최악의 경우는 62C3 이므로, 충분히 조합으로 문제를 풀 수 있다. 전체 빈 칸들 중에서 3개를 선택한 모든 경우의 수를 계산해도 되는지 먼저 파악했다. 지도의 가로, 세로 크기는 최대 8이므로, 최대 64개의 칸이 존재할 수 있고, 그 중 바이러스가 최소 2칸을 차지하므로 빈 칸의 개수는 최대 62개이다. 62개 중에서 3개를 순서 상관 없이 고르는 것이므로 위 조합이 나왔고, 대략 2^1..
https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 1. 접근 방식 (x, y) 지점의 상하좌우 지점으로부터 최단 거리를 알아낼 수 있다. 오직 가로와 세로로만 움직일 수 있으므로, 어떤 지점에서 이동할 수 있는 경로는 상하좌우밖에 없다. 예를 들어 2의 위치가 (1, 1)일 때, 이 지점의 상하좌우 즉 (0, 1), (2, 1), (1, 0), (1, 2) 지점으로부터 2까지 가는 최단 거리는 1이다...