웹개발 성장기

2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 태그는 다익스트라이지만 우선순위큐로도 풀 수 있다. (사실 우선순위큐로 풀었는데 질문글 보니 다익스트라 코드도 있어서 다익스트라로도 풀어봄...ㅎㅎ) 우선순위큐 풀이 좌표 정보 + 검은 방을 흰 방으로 바꾼 횟수를 class로 선언한 후 검은 방을 흰 방으로 바꾼 횟수가 작은 순으로 큐에서 뽑으면 된다. visited 배열로 방문 유무를 확인하며 다음 좌표가 검은방이면 cnt + 1, 흰 방이면 cnt값을 큐에 넣는다. 적은 횟수부터 탐색하기 때문에 끝방 좌표에..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 다양한 방법이 있는 것 같지만 다익스트라로 풀었다. 우선 여행 계획에 있는 도시들은 중복될 수 있으므로 순서를 배열로 입력받음과 동시에 HashSet으로 받았다. HashSet에 있는 도시들만 다익스트라 알고리즘으로 경로를 갱신했다. 만약 위치가 INF로 남아있으면 그 도시로는 방문이 불가능하다는 의미이다. 마지막으로 여행 계획에 있는 도시들을 for문으로 순회하면서 INF가 나오면 바로 "NO"를, 그렇지 않으면 "YES"를 출력하게 했다. 코드 impo..

1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 일단 이 문제는 다익스트라가 맞다. 틀려서 결국 구글링을 하긴 했는데 대부분 이분탐색과 BFS를 조합하여 했지만 이분탐색으로 풀면 뭔가 문제의 취지에 안맞는 느낌(?)이 들어서 다익스트라 코드도 찾아봤다. 다익스트라로 풀 경우 우선순위큐를 사용하여 중량 기준 내림차순으로 들어가도록 한다. 일반적인 최단경로 찾기의 경우 시작노드 기준 거리 정보를 업데이트를 하는 dist[]을 두는데, 여기선 해당 위..

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 우선순위큐를 이용한 다익스트라를 3번 실행한 후 경로가 존재하면 최단경로 출력, 없으면 -1을 출력하면 된다. 출발점, 도착점, 거치는 두 정점을 각각 A, B, X, Y라고 하면 A -> X, Y X -> Y, B Y -> X, B 이렇게 각 정점에서의 최단경로를 구한다. 최단경로는 dist[3][N + 1] 이렇게 이차원 배열을 만들어서 저장했다. A -> X -> Y -> B, A -> Y -> X -> B..