본문 바로가기

알고리즘 문제풀이/[Python] 백준

 (4)
[백준 2667번 / 실버1] 단지번호붙이기 - (Graph Traversal) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net from collections import deque def apart(data): num,cnt=0,0 result=[] queue=deque() dx=[1,0,-1,0] dy=[0,1,0,-1] for i in range(n): for j in range(n): if data[i][j]==1: queue.append([i,j]) data[i][j]=0 cnt+=1 while queue: x,y=..
[백준 13305번 / 실버4] 주유소 - (그리디) https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 처음에 풀때 시간초과가 떠서 input()을 sys.stdin.readline()으로 바꿨는데 마찬가지로 시간초과가 떴다. 한마디로 코드에 문제가 있었다는 뜻. 아래 코드는 다시 짠 코드임. 이 문제의 풀이법!!! 현재상황에서 가장 최선의 선택을 하면 되는 그리디 알고리즘 문제이다. 현재 도시를 기준으로 현재 도시보다 기름값이 더 싼 곳에 이동할때까지 현재 도시에서 주유한 기름으로 ..
[백준 2178번 / 실버1] 미로 탐색 - (Graph Traversal) 문제링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제는 최소경로를 찾는 문제이고 각각 간선(edge)의 가중치가 동일하므로 BFS를 이용해도 무방하다. 핵심은 dx,dy라는 방향벡터를 사용하는 것과, 미로의 정보를 나타내는 data라는 2차원 리스트랑은 별개로 특정 칸을 방문하기 위해 지나야 하는 최소 칸의 정보를 담고있는 visited라는 2차원 리스트를 추가로 만드는것이다. from collections import deque def BFS(data): v..
[백준 1260번 / 실버2] DFS와 BFS - (Graph Traversal) 문제링크 : 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 코드에서 굳이 visited라는 리스트를 return해 주지 않고도 코드를 작성할 수 있다. 사실 visited를 return하는 방법과 하지않는 방법 중에서 어떤것이 더 좋은 코드인지 잘 모르겠다..ㅎ from collections import deque def DFS(graph,v,visited=None): visited.app..

티스토리툴바