본문 바로가기

전체 글200

[Algorithm] 백준 16234 인구 이동 | 파이썬 BFS ※ 16234 인구 이동https://www.acmicpc.net/problem/16234문제 해결 TIP모든 나라의 위치에서 BFS를 수행하여 인접한 나라의 인구수를 확인한 뒤에, 가능하다면 국경선을 열고 인구 이동 처리를 진행한다. visited 배열을 따로 두어 index를 확인하면서 더 이상 인구 이동을 할 수 없을 때까지 반복한다. BFS를 처리할 때 인구 분배를 같이 해나가는게 중요한 것 같다.   전체 코드 from collections import dequeN, L, R = map(int,input().split())graph = []for i in range(N): graph.append(list(map(int,input().split())))#graph = [[50, 30], [2.. 2024. 7. 3.
[Algorithm] 백준 18405 경쟁적 전염 | 파이썬 BFS ※ 18405 경쟁적 전염https://www.acmicpc.net/problem/18405첫번째 문제 풀이 (시간 초과)문제를 보고 먼저 생각해낸 해결방법은1. 바이러스 번호 1번부터 graph에서 위치한 자리값을 position 배열에 저장한다.2. position 배열에서 하나씩 꺼내어 확산을 진행한다.N, K = map(int,input().split())graph = []for i in range(N): graph.append(list(map(int,input().split())))S, X, Y = map(int,input().split())#graph = [[1, 0, 2], [0, 0, 0], [3, 0, 0]]dx = [-1,1,0,0]dy = [0,0,-1,1]def bfs(x,y,.. 2024. 7. 2.
[Algorithm] 백준 11724 연결 요소의 개수 | 파이썬 DFS ※ 11724 연결 요소의 개수https://www.acmicpc.net/problem/11724문제 해결 TIP간선 정보를 이용하여 몇개의 그룹이 만들어지는지 출력하는 문제이다. 기본 DFS 알고리즘을 이용하여 풀 수 있고, 주의해야 할 점은 RecursionError가 발생하는 것이다. 1000번 이상의 recursion이 발생하면 recursion error 가 뜨기 때문에 recursionlimit을 변경해주었다. 전체 코드import syssys.setrecursionlimit(10**7)input = sys.stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]for i in range(M): u, v .. 2024. 6. 30.
[Algorithm] 백준 10026 적록색약 | 파이썬 BFS ※ 10026 적록색약https://www.acmicpc.net/problem/10026문제 해결 TIP유기농 배추 문제와 같이 처음에 DFS로 풀다가 RecursionError에 걸려서 BFS로 바꾸었다. 적록색약인 것과 아닌 것의 그래프를 애초에 따로 저장하여 bfs로 돌려주었다. 전체 코드from collections import dequedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]N = int(input())graph = [] #적록색약이 아닌 그래프for i in range(N): graph.append(list(map(str,input())))new_graph = [row[:] for row in graph] #적록색약이 보는 그래프# 새로운 그래프에서 'G' 값을.. 2024. 6. 29.
[Algorithm] 백준 7576 토마토 | 파이썬 BFS ※ 7576 토마토https://www.acmicpc.net/problem/7576문제 해결 TIP이코테의 미로 탈출과 비슷한 문제라고 생각했다. BFS를 이용하여 토마토를 전염시킨 후 최단 거리를 반환하는 것과 같이 전염하면서 이전 값에 1을 추가하여 값을 저장하도록 한다. 이때 주의할 점은 2차원 배열의 첫번째 원소부터 탐색 시작하는 것이 아닌, 1을 가진 토마토라면 동시에 전염이 시작되어야 한다는 것이다. 최종적으로 바뀐 2차원 배열 graph에 익지 않은 토마토가 있다면 -1을 반환하고 그렇지 않으면 최소 일수(graph에서 가장 큰 원소값-1)를 반환한다. 이때 이미 처음부터 모든 토마토가 익어있는 상태라면 0을 출력하게 되어있는데, 어차피 graph에서 가장 큰 원소값이 1일테니 0을 반환할 .. 2024. 6. 27.
[Algorithm] 백준 1012 유기농 배추 | 파이썬 BFS ※ 1012 유기농 배추https://www.acmicpc.net/problem/1012문제 해결 TIP처음에 DFS로 풀다가 RecursionError에 걸려서 BFS로 바꾸었다. 바이러스 문제와 비슷하게 상하좌우 주변 노드들을 방문하며 큐에 삽입하고 탐색하는 방법으로 진행한다. 여기서 주의할 점은 문제에서 가로 길이를 M, 세로 길이를 N으로 주어진 점이다. 전체 코드from collections import dequedx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def bfs(x, y): queue = deque() queue.append((x, y)) while queue: x, y = queue.popleft() for i in rang.. 2024. 6. 26.
[Algorithm] 백준 2667 단지번호붙이기 | 파이썬 DFS ※ 2667 단지번호붙이기https://www.acmicpc.net/problem/2667문제 해결 TIP이코테의 음료수 얼려 먹기 문제의 응용 버전이라고 생각하면 된다. DFS를 이용하여 연결된 모든 노드들을 방문하고 count를 해준다. 집이 있는 곳이라면, 문제에 나와 있는 것처럼 단지번호를 붙여준다. (집의 유무인 1과 헷갈리지 않기 위해 단지번호는 2부터 붙여주었다.) 집을 모두 방문한 후 그래프의 최종 상태는 마지막 주석을 확인하기 바란다. 전체 코드N = int(input())graph = []for i in range(N): graph.append(list(map(int,input())))#graph = [[0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 0, 1, 0, 1].. 2024. 6. 26.
[Algorithm] 백준 2606 바이러스 | 파이썬 BFS ※ 2606 바이러스https://www.acmicpc.net/problem/2606문제 해결 TIP너비우선 탐색 알고리즘인 BFS를 이용하여 쉽게 풀 수 있다. 1번 컴퓨터부터 큐에 삽입하여 주변 노드들을 방문 처리해준다. 전체 코드from collections import dequeN = int(input())M = int(input())graph = [[] for _ in range(N + 1)]# 그래프 변환 작업for _ in range(M): node1, node2 = map(int, input().split()) graph[node1].append(node2) graph[node2].append(node1)#graph = [[],[2, 5], [1, 3, 5], [2], [.. 2024. 6. 26.
[Algorithm] 이코테 만들 수 없는 금액 | 파이썬 (그리디) [문제]동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다. [입력 조건]첫 째줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1≤N≤1,000)둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분합니다.. 2024. 6. 24.

티스토리툴바