목록dfs (8)

개미의 개열시미 프로그래밍

[프로그래머스] LEVEL2 타겟넘버 - 자바

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr [DFS 풀이 - 재귀] // 재귀풀이 class Solution { static int cnt=0; public int solution(int[] numbers, int target) { dfs(0, 0, numbers, target); return cnt; } static void dfs(int idx, int sum, int[] nu..
알고리즘/DFS, BFS, 백트래킹 2022. 2. 9. 23:05
[알고리즘] 백준2206 벽 부수고 이동하기 - 파이썬

이번 문제는 단계별 풀기 bfs, dfs파트에 7번째 문제인 벽 부수고 이동하기 문제입니다. https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 코드 # 벽을 하나 부쉴 수 있다는 점 # 불가능이면 -1 # 최단거리 = bfs from collections import deque from sys import stdin n, m = map(int, stdin.readline().split()) graph = [] for..
알고리즘/DFS, BFS, 백트래킹 2021. 6. 8. 14:32
[알고리즘] 백준1697 숨바꼭질 - 파이썬

오늘은 단계별로 풀어보기 'bfs와 dfs' 파트 중 7번째 문제입니다. 앞으로 세문제 정도 남았는데 시험기간이 끝나면 하루 두 세 문제씩 해서 모든 파트를 빨리 끝내고 싶습니다. https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이코드 # 예시 5 - 10 - 9 - 18 - 17 # 가장 빠른 시간을 출력하기 => 가장 빠른 거리를 찾는 문제와 유사하다고 생각 => bfs문제 from collections impo..
알고리즘/DFS, BFS, 백트래킹 2021. 6. 7. 20:05
[알고리즘] 백준2178 미로탐색 - 파이썬

오늘은 백준 단계별 풀기 dfs, bfs 파트 5번째 문제입니다. 이코 테에서 풀었던 미로 탈출 문제와 거의 유사해서 금방 풀 수 있을 거라 생각했지만 사소한 부분에서 실수를 해서 시간이 조금 걸렸습니다. 하지만 복습한다고 생각하고 다시 짚고 넘어갈 수 있어서 좋았습니다. 복습이 필요하다고 생각했는데 이렇게 같은 유형을 반복적으로 푸는것도 복습이 된다고 생각합니다. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이코드 # bfs, deque from collections ..
알고리즘/DFS, BFS, 백트래킹 2021. 6. 2. 14:48
[알고리즘] 백준 1012 유기농 배추 - 파이썬

기말고사 시즌이지만 시험공부가 너무 하기싫어서 한문제 더풀었다.. 처음에는 쉽게 풀리는 듯 했으나 이상하게 입력으로 가로, 세로 바꿔놓으면 헷갈린다.. 문제에서 가로를 m, 세로를 n으로 입력 받게 되어 있다. 난 아무생각없이 가로를 n 세로를 m으로 입력받고 혼자 중간에 패닉에 빠졌다.. https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이코드 1. DFS풀이 from sys import stdin import sys sys.setrecursionlimi..
알고리즘/DFS, BFS, 백트래킹 2021. 6. 1. 18:09
[알고리즘] 백준 2667 단지번호붙이기 - 파이썬

오늘은 백준의 단계별 풀어보기에서 DFS와 BFS단계 단지 번호 붙이기 문제를 풀어보았습니다. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 코드 n = int(input()) # 지도의 크기 graph = [] for _ in range(n): graph.append(list(map(int, input()))) cnt = 0 # 단지내 집의 수 카운트 cnt_list = [] # 하나의 단지내 집의 수를 담을 리스트 #dfs, 스택, 재..
알고리즘/DFS, BFS, 백트래킹 2021. 6. 1. 14:12
[알고리즘] 백준 1260 DFS와 BFS - 파이썬

어제 공부했던 DFS, BFS문제를 이어 풀어보았습니다. 백준 단계별 풀기에서 'BFS, DFS' 문제가 11문제 정도되는데 학기중이니 하루에 한문제씩이라도 꾸준히 풀생각입니다. https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque from sys import stdin n, m, v = map(int, stdin.readline().split()) graph..
알고리즘/DFS, BFS, 백트래킹 2021. 5. 30. 17:50
[알고리즘] 이코테 음료수 얼려 먹기, 미로탈출 - 파이썬

이제 코딩 테스트를 본격적으로 공부하려 한다. 원래 학기가 끝나고 준비하려 했지만 왠지 모를 불안감에 시작했다.. 친구가 알려준 순서와 나동빈의 이코 테를 참고해서 같이 공부하려 한다. 친구가 알려준 알고리즘 공부 순서는 '백 트랙킹, DFS, BFS, 브루트 포스, 유니온 파인드 기타 자료구조(큐, 스택, 리스트)'이고 이코테에서는 백트래킹 부분이 없어서 따로 유튜브 강의를 보고 백준을 풀 생각이다. 먼저, 오늘은 BFS와 DFS를 공부했고 표로 간단히 정리하면 아래와 같다. DFS BFS 동작원리 스택 큐(dequeue) 구현방법 재귀 함수 이용 큐 자료구조 이용 주의할 점은 BFS문제를 풀때 dequeue를 활용한다는 점이다. 문제 1) 음료수 얼려먹기 # 입력받기 n, m = map(int, in..
알고리즘/DFS, BFS, 백트래킹 2021. 5. 30. 00:31
Prev 1 Next