본문 바로가기
728x90
반응형

알고리즘 공부69

[BOJ] 1504번 특정한 최단 경로 / 사용언어 : 파이썬(python) ※ 문제링크 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net ※ 관련개념 23. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐... blog.naver.com 해당 문제는 가중치가 있는 최단거리 계산 문제로 다익스트라 알고리즘을 활용해서 풀 수 있는 문제였다. 다익스트라 알고리즘을 파이썬에서 구현하기 위해 heapq를 사용하여 우선순위 큐 자료구조를 구현하였.. 2022. 1. 16.
[BOJ] 10026번 적록색약 / 사용언어 : 파이썬(python) ※ 문제링크 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 해당문제는 BFS로 해결할 수 있는 문제였다. 구현할 때 정상인 사람의 경우에는 입력좌표값과 상, 하, 좌, 우 좌표값의 색이 완전히 일치할때만 연결해주고, 적록색약의 경우 R, G의 경우는 통합시켜서 연결해주면 쉽게 해결할 수 있는 문제였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력값을 2차원 배열의 형태로 변환시켜준다. 2. 정상인 사람과 적록색약인 사람을 나누어서 각각 탐색할 BFS함수를 작성해준다. 3. 결과값을 출력해준다. +.. 2022. 1. 15.
[BOJ] 1753번 최단경로 / 사용언어 : 파이썬(python) ※ 문제링크 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net ※ 참고사이트 [백준] 1753번(python 파이썬) 문제 링크: https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정.. pacific-ocean.tistory.com 해당문제는 다익스트라 알고리즘을 활용하여 풀 수 있.. 2022. 1. 15.
[BOJ] 4963번 섬의 개수 / 사용언어 : 파이썬(python) ※ 문제링크 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 해당 문제는 BFS를 사용해서 해결할 수 있는 문제였다. 문제에서 상,하,좌,우 뿐만아니라 대각선까지도 이동가능하다는 점만 신경써서 코드를 작성하면 비교적 간단하게 해결할 수 있어서 해당방식으로 코드를 작성하였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력값을 바탕으로 2차원 배열로 지도형태를 구현한다. 2. 이어져 있는 섬들을 탐색할 수 있는 BFS함수를 작성한다.(방문한 섬의 경우 2로 변경하여 방문여부를 표기했다.) 3. 배열의 크.. 2022. 1. 15.
[BOJ] 18352번 특정 거리의 도시 찾기 / 사용언어 : 파이썬(python) ※ 문제링크 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 해당 문제는 BFS를 사용해서 풀 수 있는 문제였다. 문제분류는 다익스트라 알고리즘으로 분류되어 있으나 BFS만 사용할 줄 알아도 풀 수 있는 문제였다. 풀이방법을 간단하게 이야기하면 입력값을 바탕으로 딕셔너리를 사용해서 그래프를 구현한 후, 반복문을 통해 간선으로 이어진 도시들을 방문하면서 방문여부를 체크하고, 요구받은 거리값까지 반복문을 돌렸을때 남는 값을 출력하면 된다. 자.. 2022. 1. 14.
[BOJ] 14502번 연구소 / 사용언어 : 파이썬(python) ※ 문제링크 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 해당문제는 DFS와 BFS를 활용하여 풀 수 있는 문제였다. 문제 조건에서 반드시 벽 3개를 설치해야한다고 하였기에 입력값을 배열로 전환하고 벽을 세울 수 있는 조합수를 DFS를 통해 구한 후 조합수별로 배열을 따로 만들어서 조합수만큼 반복문을 돌려 바이러스가 퍼지지 않은 최댓값을 구하려고 하였다. 처음에는 배열을 다 만든다음 한번 더 완전탐색을 해서 바이러스가 퍼지지 않은 지역 개수의 최댓값을 구하려고 했으나, 생각보다 시간과 메모리 조건이 까다로운 것 같아 B.. 2022. 1. 14.
[BOJ] 11724번 연결 요소의 개수 / 사용언어 : 파이썬(python) ※ 문제링크 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net ※ 참고사이트 [그래프] 연결 요소 연결 요소에 대한 개념 정리와 백준 11724번: 연결 요소 문제 풀이 velog.io 해당 문제는 BFS로 해결할 수 있는 문제였다. 우선 연결 요소의 개념을 알아야 했기에 구글링을 통해 해당 개념을 확인하고, 문제를 해결하였다. 처음에 문제를 해결할때 간선이 없는 정점에 대해서는 고려하지 않아 오답을 받았다. 이후에는 해당 부분을 수정해주고, 생각한대.. 2022. 1. 13.
[BOJ] 1707번 이분 그래프 / 사용언어 : 파이썬(python) ※ 문제링크 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ※ 관련개념 [알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 해당 문제는 BFS로 해결할 수 있는 문제였다. 해결을 위해서는 우선 이분 그래프의 개념에 대해서 먼저 이해해야 했고, 해당 개념을 이해하기 위해 구글링을 하던 중 이해하기 쉽게 정리해준 글이 있어 해당 글을 참조한 후 코드를 작성하였다. 서로 .. 2022. 1. 12.
[BOJ] 2206번 벽 부수고 이동하기 / 사용언어 : 파이썬(python) ※ 문제링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 해당문제는 BFS를 활용하여 해결할 수 있는 문제였다. BFS구현을 위해 collections의 deque를 활용하였고, 시간 단축과 메모리 절감을 위해 sys를 사용하였다. 처음에는 방문여부만 확인하면서 작성하면 해결할 수 있을 거라 생각하여 코드를 작성했지만, 벽을 부수고 이동했을 경우와 벽을 부수지 않고 이동했을 경우를 나누어 생각해야하는 문제였기에 해결에 실패하였다. 이후에는 변수들을 고려하여 다시 코드를 작성하였고,.. 2022. 1. 11.
728x90
반응형

티스토리툴바