본문 바로가기

DFS10

[백준/21736/JavaScript] 헌내기는 친구가 필요해 풀이 (dfs, bfs, 자바스크립트, js) [백준/21736/javascript] 헌내기는 친구가 필요해 풀이( dfs, bfs, 자바스크립트, js) 1. 문제https://www.acmicpc.net/problem/21736 2. 문제 풀이 1. BFS 1. 큐에 시작 지점 위치를 저장한다. (I) 2. 큐가 빌 때까지 BFS를 반복한다. BFS는 ' 이동하게 될 위치를 기준으로' 확인한다. 2.1. 상,하,좌,우 탐색- 주어진 범위 (n,m)를 벗어나면 continue- 'X'이면 벽이므로 continue- 'P'이면 사람이므로 1 추가- 'O'거나 'P'이면 새로운 위치에 있는 값을 찾은 사람 수로 업데이트하고, 큐에 새로운 위치 좌표 추가 (방문처리) 2. DFS1. 시작 지점(I)에서 DFS를 수행한다. DFS는 '이동한 위치.. 2025. 6. 5.
[프로그래머스/파이썬] 타겟 넘버 중복순열 풀이 (Python, product, 반복문) [프로그래머스/파이썬] 타겟 넘버 중복순열 풀이 (Python, product, 반복문) 1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 2. 문제 해결 아이디어 (풀이) 1. 중복순열로 [+.- ]로 이루어진 모든 순열을 구한다. 2. 구한 순열을 순회하면서, +/- 를 비교하여 더하거나 빼는 것을 계산한다. 3. 결과가 target과 같다면, 결과 +1을 진행한다. 3. 코드from itertools import product# 중복순열 def solution(numbers, t.. 2025. 5. 8.
[프로그래머스/파이썬] 전력망을 둘로 나누기 풀이 (dfs, 완전탐색, python) [프로그래머스/파이썬] 전력망을 둘로 나누기 풀이(dfs, 완전 탐색, python) 1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/86971 2. 문제 해결 아이디어 일단, 송전탑들은 모두 전선 하나씩으로 연결되어 있다.그렇기에 전선을 한 개를 끊으면 전력망은 2개가 된다. 그렇기 때문에, 전선을 끊었을 때 A,B 두 개로 나눠진 전력망을각각 DFS를 이용하여 연결된 전력망을 따라 송전탑의 개수를 구하면 된다.**이때, dfs를 사용하기 위해 wires 배열을 그래프 구조로 새로 만들어줘야 한다.**또한, 노드별 방문여부를 저장하는 배열을 한 개 만들어줘야 한다. 3. 코드# False : 방문안함# True : 방문함 import s.. 2025. 5. 6.
[프로그래머스/파이썬] 네트워크 풀이 ( dfs , 재귀함수, Python ) [프로그래머스 / 파이썬] 네트워크 풀이 ( dfs , 재귀함수, Python )  1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 2. 문제 해결 아이디어 (풀이)  1. 반복문으로 모든 노드를 1~n번까지 DFS로 탐색하면서, 하나의 노드 당 연결된 모든 노드를 방문처리한다.* 이때, 방문 처리 배열 'visited'를 만들어서 이용한다.  1.1. 이때 현재 노드와 연결된 모든 노드를 for문으로 반복하여서, 아직 방문하지 않은 노드인지(+ 벽이 아닌 길인지) 확인한 뒤, df.. 2025. 3. 1.

티스토리툴바