본문 바로가기
728x90
반응형

개발공부74

[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.
[BOJ] 7562번 나이트의 이동 / 사용언어 : 파이썬(python) ※ 문제링크 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 해당문제는 BFS를 활용하여 풀 수 있는 문제로, deque를 활용하여 BFS를 구현하여 해결을 하였다. 체스의 나이트의 이동조건을 알고 있는 사람이라면 보다 쉽게 해결할 수 있는 문제로 방문한 위치를 기록하고 목표점에 도달했을때에 반복문을 종료하는 방식으로 해결할 수 있었다. 자세한 문제풀이와 코드는 아래와 같다. 1. 입력받은 값을 바탕으로 반복문을 작성하고, 체스판을 작성하여 출발점만 1로 표기해준다. 2. 나이트의 최초위치와 목표점과 같을때에는.. 2022. 1. 10.
[BOJ] 1697번 숨바꼭질 / 사용언어 : 파이썬(python) ※ 문제링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해당 문제는 BFS를 활용하여 풀 수 있는 문제였다. BFS 구현을 위해 collections의 deque를 사용하였으며, 문제에서 주어진 이동조건을 구현하기 위해 간단하게 함수를 작성하였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 N값을 deque리스트에 삽입하여주고, 이미 방문한 숫자들을 제외하기위해 방문여부를 확인할 배열을 작성해준다. 2. 이동할 수 있는 경우는 기본적으로 3개이기에 deque활용하여 .. 2022. 1. 10.
[BOJ] 7576번 토마토 / 사용언어 : 파이썬(python) ※ 문제링크 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 해당문제는 BFS를 활용하여 풀 수 있는 문제였다. BFS를 구현하기 위해 파이썬에 내장되어 있는 collections의 deque를 사용했다. 기존의 문제들과 조금 차별점이 있다면 시작점이 1개가 아니라 여러개가 될 수 있다는 점이었기에 해당 부분에 초점을 두고 문제를 해결하였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 2차원 리스트 형태로 변환한다. 2. 배열의 처음부터 마지막까지 2중 반복문을 이용하여 탐색.. 2022. 1. 9.
[BOJ] 2178번 미로 탐색 / 사용언어 : 파이썬(python) ※ 문제링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 해당 문제는 BFS를 활용하여 풀 수 있는 문제였다. DFS를 메모이제이션을 활용하여 기록하면서 풀면 답을 구할 수는 있으나, 시간 및메모리가 과도하게 사용되기에 BFS로 해결하기로 생각하였다. 문제조건 중 무조건 탈출이 가능하다는 전제조건이 주어졌기에 BFS함수를 작성하고 시작점에서 함수를 한번만 실행하는 방식으로 해결하였다. 자세한 문제풀이방법과 코드는 아래와 같다. 1. 입력받은 값을 2차원 배열로 변환하여 준다. 2. 파이썬 내장함수인 dequ.. 2022. 1. 7.
728x90
반응형

티스토리툴바