본문 바로가기

dfs3

[프로그래머스 Lv3] : 네트워크 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 여러대의 컴퓨터가 연결되어 있을 때, 서로 정보를 교환할 수 있는 컴퓨터들의 그룹을 네트워크라고 한다. 네트워크의 총 개수를 세어보자. 풀이 컴퓨터가 직접적으로 연결되어있지 않아도 간접적으로 정보를 교환할 수 있어도 같은 네트워크에 있는 것으로 간주한다. 이 문제는 백준에 있는 유기농배추 문제와 비슷한 문제인 듯하다. 참고 링크 https://w.. 2022. 6. 20.

[BOJ] 14529 : Where's Bessie? 문제 링크 14529번: Where's Bessie? (acmicpc.net) 14529번: Where's Bessie? Always known for being quite tech-savy, Farmer John is testing out his new automated drone-mounted cow locator camera, which supposedly can take a picture of his field and automatically figure out the location of cows. Unfortunately, the camera does not in www.acmicpc.net 브루트포스 기법으로 모든 크기의 구역을 탐색하는 그래프탐색 문제. 문제 해석 파파고까지 쓰면서 해석했지.. 2022. 4. 29.

[BOJ] 1937 : 욕심쟁이 판다 문제 링크 1937번: 욕심쟁이 판다 (acmicpc.net) 풀이 문제를 보면 일단 DFS문제라는 것을 알 수 있다. 시작점에서 상하좌우 중 범위를 벗어나지 않으면서 현재 지점보다 값이 크면 그 지점을 방문한다. 그렇게 해서 더 이상 이동할 수 없을때 까지 도달했을 때 그 깊이 중 가장 큰 값을 찾는 문제이다. 그런데 모든 점에서부터 출발해서 최대값을 찾으면 될까?? 당연히 아니다. 그렇게 하게되면 이미 방문했던 지점을 시작점으로 같은 경로를 재탐색 하게되는 경우가 발생하기 때문에 시간초과가 난다. 그럼 어떻게 해야할까? DP를 이용해서 재방문을 하지 않도록 해야한다. 예제를 보자 4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8 (1,1)을 출발점으로 했을 때 주변에 자신(14.. 2022. 3. 1.

이전 1 다음

티스토리툴바