본문 바로가기

알고리즘

[백준] 13460: 구슬 탈출 2 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 이번 문제는 bfs로 풀었습니다. 구현 자체가 이전 문제들보다는 난이도 있어서 구현에 시간을 생각보다 많이 사용하였습니다. 사실 원래 dfs를 연습할 생각으로 문제를 보고 dfs로 풀어야지 라는 강박에 잡혀 시간을 허비하다가 다른 사람들의 코드를 참고하여 풀게 되었습니다. 그렇기에 주석을 이번엔 자세히 많이 첨부하면서 소스 코드를 되뇌이게 되었습니.. 더보기
[백준] 5014번: 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이제는 어느 정도 bfs의 감을 잡은 것 같다. 그리고 중요한 것은 역시나 예외 상황 처리가 가장 중요하다. 간단하지만 if의 조건을 쓸 때 앞 쪽에 예외처리를 해줘야하고 불가능한 수들을 다양하게 생각해야 한다. from collections import deque f, s, g, u, d = map(int,input().split()) answer = -1 arr = [0 for i in range(1000.. 더보기
[백준] 1697번: 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 마찬가지로 bfs로 해결하였다. 경우의 수를 다 해보는 방식으로 조금 더 발전시켜서 점화식을 찾는다면 dp로 풀 수 있을 것 같다. from collections import deque start, end = map(int,input().split()); arr = [0 for i in range(0,100001)] q = deque([]) q.append([start,.. 더보기
[백준] 2644번: 촌수계산 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 코딩테스트 전 이전에 공부한 bfs 개념을 되돌아보기 위해 풀어보았다. deque를 사용하여 popleft를 사용할 수 있게하였다. from collections import deque answer = -1 flag = 0 n = int(input()); start, end = map(int,input().split()); m = int(input()); arr = [[0 fo.. 더보기
[백준] 2667번: 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이전에 풀었던 문제보다 쉽게 구현이 가능한 문제이다. bfs탐색을 연습하기 위해 bfs로 구현하였다. dfs로 구현하여도 클리어는 가능한 문제로 보인다. 또한 이번에는 단순 list,pop(0)을 이용하지 않고 deque를 선언하여 구현하였다. from collections import deque n = int(input()) arr = [] for i in range(n): arr.append(l.. 더보기
[백준] 7576번: 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net bfs로 최단거리 탐색을 활용하면 쉽게 풀 수 있다. 이 문제를 풀면서 list로 pop,append를 사용하는 것 보다 deque()로 선언을 하여 돌려주는 것이 훨씬 빠르다는 것을 알았다.(list로 pop을 할 때 전체 list를 서치하게 됨) from collections import deque m,n = map(int,input().split()) arr = [] for .. 더보기
[백준] 2178번: 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제는 bfs최단 경로를 구하는 문제였다. 그 동안은 그래프 문제를 대부분 dfs를 먼저 적용하고 익숙하게 사용하였는데 이번 문제는 dfs로 구현할 경우 가지치기를 많이 번거롭게 많이하지 않는 이상은 구현이 거의 불가능하다. 그러므로 bfs를 연습할 겸 bfs로 구현하였다. 이 문제를 그래프의 기초를 더 다지기 위해 bfs문제로 양방향 관련 문제를 풀어봐야겠다. n,m = map(int,input().split()) min .. 더보기
[백준] 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이번 문제는 가장 기본적인 그래프 알고리즘 구현 문제이다. 양방향 처리에 대하여 풀려다가 우선 기본부터 다지자는 생각으로 이 문제를 선택하였다. dfs는 흔하게 사용하던 기법으로 기존과 같이 사용하여 재귀로 구현하였고 bfs를 큐형태로 만들어 구현하는 것이 새로웠다. 사용방법을 꼭 숙지하고 있어야겠다. 그리고 리스트를 문제에 맞게 큰 NxN개의 2차원 배열로 .. 더보기

티스토리툴바