본문 바로가기
반응형

Study/Algorithm38

[백준] #7576. 토마토 (python) - bfs 파이썬 풀이 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 .. 2024. 4. 20.
[백준] #1926. 그림 (python) - bfs 풀이 문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다. 입력 첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 .. 2024. 4. 20.
[Algorithm] 플로이드-워셜(floyd-warshall) 알고리즘 (python) 플로이드-워셜 알고리즘 플로이드-워셜 알고리즘은 최단 거리를 구할 때 사용하는 알고리즘이다. 벨만-포드 알고리즘과 같이 음수 가중치를 가지는 노드가 있어도 사용가능하다. 하지만 벨만-포드 알고리즘보다 더 큰 시간 복잡도를 가진다. 플로이드-워셜 알고리즘의 핵심 원리는 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합이라는 것이다. 파이썬으로 플로이드-워셜 알고리즘 구현하기 1. 최단 거리를 저장할 2차원 리스트 선언 출발 노드와 도착 노드가 같은 경우는 0으로 초기화하고 기본은 시스템 최댓값으로 초기화한다. dist=[[sys.maxsize]*(n+1) for _ in range(n+1)] for i in range(1, n+1): dist[i][i]=0 2. 주어진 그래프 값 저장 1에서 선언한 .. 2023. 2. 9.
[백준] #1976. 여행 가자 (python) 문제 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라.. 2022. 12. 16.
반응형

티스토리툴바