목록알고리즘/DFS, BFS, 백트래킹 (48)

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

[알고리즘] 백준7569 토마토 - 파이썬

이번에는 저번에 풀었던 토마토를 3차원 배열을 활용해서 풀어야 하는 문제였습니다. 쉽게 풀 수 있을 거라 생각했지만 bfs로 위, 아래, 왼쪽, 오른쪽, 앞, 뒤를 탐색하는 부분에서 막혔고 풀이를 보면서 제 방식대로 다시 풀어보았습니다. https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이코드 from collections import deque import sys input = sys.stdin.readline # 위,..
알고리즘/DFS, BFS, 백트래킹 2021. 6. 6. 19:24
[알고리즘] 백준7576 토마토 - 파이썬

어제 점심에 풀었던 문제였지만 졸업 프로젝트 포스터를 만들고 다른 과목 발표자료도 만드느라 이제야 글을 올린다.. https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이코드 from collections import deque from sys import stdin m, n = map(int, stdin.readline().split()) # m가로, n세로 graph = [] for _ in range(n): graph.appe..
알고리즘/DFS, BFS, 백트래킹 2021. 6. 4. 04:08
[알고리즘] 백준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
[알고리즘] 백준 2606 바이러스 - 파이썬

오늘도 백준의 단계별 풀기에서 DFS, BFS에 관한 문제를 풀어보았습니다. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net from collections import deque from sys import stdin n = int(input()) # 컴퓨터의 수 m = int(input()) # 연결된 수 graph = [[0] * (n+1) for _ in range(n+1)] # 인접행렬 생성 for _ in range(m): x, y = ma..
알고리즘/DFS, BFS, 백트래킹 2021. 5. 31. 15:19
[알고리즘] 백준 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 ··· 3 4 5 6 Next