본문 바로가기
728x90
반응형

BOJ71

[BOJ] 2146번 다리만들기 / 사용언어 : 파이썬(python) ※ 문제링크 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 해당문제는 BFS를 활용하여 해결할 수 있는 문제였다. 처음 생각한 방법은 완전 탐색을 통해 섬의 좌표값을 모두 확인한 후 BFS함수를 한번씩 돌려가며 다른 섬에서 출발한 다리와 만날때 cnt값을 반환하는 것이었는데, 해당 방식으로 구현하면 다리의 길이가 될 수 있는 경우의 수가 2개가 되어 정확한 값을 구하지 못하는 문제가 있어 각 섬에 고유번호를 부여하고, 맵의 각 좌표의 방문기록을 일일히 기록하며, 섬의 번호가 다른 지점이 발생할 때, 각 섬에서 출.. 2022. 1. 18.
[BOJ] 9370번 미확인 도착지 / 사용언어 : 파이썬(python) ※ 문제링크 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net ※ 관련개념 23. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐... blog.naver.com 해당 문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 문제에서 주어진 시간 조건과 메모리 조건이 생각보다 여유롭다고 판단하여 BOJ 1504번에서 사용했던 개념을 그대로 가져와 살짝 변형하여 해결코드를 구현하였고, 테스트 결과 .. 2022. 1. 17.
[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.
728x90
반응형

티스토리툴바