https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 Level 3 정도의 문제지만, 백준으로 치면 다른 트릭이나 복잡한 구현이 없는 기본적인 bfs/dfs 문제라서 골드 4-5정도 될 것 같다. 아무튼, 이 문제의 풀이에 대해 알아보자 문제에서 찾고자 하는 것은 '연결된 영역의 개수' 라고 할 수 있다. n은 반드시 1 이상, 즉 주어진 그래프에는 노드 1이 반드시 존재함을 알 수 있다. 1을 기점으로, 재귀 형식의 dfs를 이용해 아..
https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그래프 문제이다 딱히 추가적으로 구현해야 할 건 없고, 양방향 그래프를 잘 입력받은 뒤 bfs로 탐색을 해주면 된다 간선에 가중치가 붙으면 다익스트라를 이용해주면 된다 from collections import deque def solution(n, edge): answer = 0 graph = [[] for _ in range(n+1)] visited = [False] *(n+1) dist = ..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 오랜만에 푼 bfs 문제이다. 보물의 위치가 정해져있지 않기 때문에, 브루트포스를 이용하여 보물의 위치를 정해주는 것이 필요하다. 모든 육지(L)에 대해 bfs 탐색을 진행해주는데, 첫번째 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이가 5라고 할 때, bfs함수는 5를 반환하고 ans 변수에 저장한다. 지도를 초기화해준뒤, 2번째로 만나는 L에 대해 bfs 탐색을 하고 얻게 된 가장 긴 길이..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 맨날 다익스트라나 bfs만 연습하다가 오랜만에 풀어본 dfs문제이다. dfs를 익히기에 아주 좋은 문제라고 생각되어 포스팅해본다! 크게 어렵지도 않아서 dfs에 능숙하지 않은 나같은 사람도 잘(?) 풀 수 있으리라 생각한다. 풀이 1. 우선, R x C 모양의 보드를 입력받아준다. 2. 그리고 0,0 위치(=시작 위치)도 말이 갈 수 있는 칸 중 하나로 친다고 하였으므로 해당 위치의 알파벳..
문제를 찾아보면 알겠지만 N개의 마을에 사는 N명의 학생들이 특정한 한 집에 모여 파티를 하고, 다시 집으로 돌아가는데 드는 비용 중 최대 비용을 구하는 것이다. 다익스트라 코드는 기본적인 코드이며, 우선 특정한 한 집(코드에서는 x)에서 각각 학생들의 집까지 거리를 구하기 위해 start를 x로 하고 다익스트라를 통해 최소신장트리를 구한다. 그리고 배열 하나를 만들어서 x마을부터 각 학생들의 집(1,2,...,N)까지의 최소거리를 더한다. 다시 for문을 반복하여 각각의 학생들(i번째 학생들)에 대해 다익스트라를 실행 한 뒤, 특정한 집(변수 x)에 도달하기까지 걸리는 최소비용을 구해서 배열에 더해준다. 최소비용중 최대를 구해야하므로 변수 res를 하나 두어 최대를 뽑아낸다. res를 처음에 0으로 초..
