분류 전체보기

[python] 백준 - 2178. 미로 탐색

문제 해결 1. BFS 기본 문제. S1 2. 출발점을 1로 만들고 한칸씩 전진하며 1씩 더해준다. - BFS 이용 (1) 4 방향 탐색을 위해 dx, dy 를 만든다 ( 상하좌우). (2) 리스트(여기서는 디큐를 사용함)에 출발점을 넣어준다. (3) 탐색이 언제 끝날지 모르니까 while 문을 사용한다. (4) 리스트에서 pop(0)(여기서는 popleft())을 이용해 하나씩 꺼내준다. ( 0번을 꺼내는 이유는 BFS 기법을 사용해야 하기 때문에) (5) 꺼낸 지점에서 4방향 탐색을 해준다. (6) 탐색한 곳(nx, ny)이 '1' 인 경우 그 칸에 현재 칸(x, y) 숫자의 +1을 해주고, 리스트에 append해준다. (7) (4)번부터 다시 반복한다. 3. 각 숫자가 이동한 칸의 갯수를 나타낸다...

[python] 백준 - 1051. 숫자 정사각형

문제 해결 1. (부르트포스) 완전탐색 문제이다. 2. '가장 큰' 정사각형을 구하라고 했으므로 만들수 있는 최대 크기에서부터 하나씩 줄여나갔다.(시간 효율) 3. 네 꼭지점의 크기가 같을 때 return + break를 걸어주어 바로 탐색을 종료 + 난이도가 적당한 2차원배열 + 완전탐색 문제이다. 소스 코드 def find_squre(s): # 정사각형의 꼭지점의 숫자 크기가 같은 경우를 찾는다. for i in range(n-s+1): for j in range(m-s+1): if numbers[i][j] == numbers[i][j+s-1] == numbers[i+s-1][j] == numbers[i+s-1][j+s-1]: return True return False n, m = map(int, ..

[python] SWEA - 1251. 하나로 / 1486. 장훈이의 높은 선반

1. 하나로 문제 해결 1. 프림 + 힙큐 2. 인접리스트를 만들어 준다. 3. 힙큐를 이용해 가중치가 가장 낮은 점을 선택하고 4. key 리스트를 최솟값으로 갱신해가며 결과를 더해준다. 🔨 인접 행렬로 하다가 몇시간 날린 것 같다. 역시 난 인접리스트를 쓰는게 편하다. 소스 코드 import heapq for tc in range(1, 1+int(input())): n = int(input()) x_location = list(map(int, input().split())) y_location = list(map(int, input().split())) tax = float(input()) # 인접 리스트 adj = {i: [] for i in range(n)} for s in range(n): fo..

[python] SWEA - 1249. 보급로 / 5521. 상원이의 생일파티

1. 보급로 문제 해결 1. 다익스트라 알고리즘 + 힙큐 2. 가중치 리스트와 방문 리스트를 만들어 준다. 3. 힙큐를 이용해 가중치가 가장 낮은 점을 선택하고 4. 주변을 탐색하여 최소 가중치를 선택해 가중치를 점점 누적해 나아간다. 소스 코드 import heapq for tc in range(1, 1+int(input())): n = int(input()) maps = [list(map(int, list(input()))) for _ in range(n)] # dist: 가중치를 누적한 리스트, visit: 선택했는지 안했는지 dist = [[float('inf')]*n for _ in range(n)] visit = [[False]*n for _ in range(n)] dx, dy = [-1, 1..

[python] 백준 - 16236. 아기 상어 (삼성 SW 역량 테스트 기출 문제)

문제 해결 1. BFS를 활용한 시뮬레이션 문제이다. (게임 같은 문제) 2. 먼저 상어의 위치, 레벨, 먹은 물고기수, 총이동거리 등을 정의 해준다. 3. 상어의 레벨에 따른 먹을 수 있는 물고기를 찾는다. 4. 물고기를 찾으면 (1) 거리가 가장 가까운 물고기 (2) 그런 물고기가 여러마리이면 가장 위에 있는 물고기 (3) 그런 물고기가 여러마리이면 가장 왼쪽에 있는 물고기를 선택한다. (sort함수를 사용하면 쉽게 얻을 수 있다.) 5. 먹을 물고기를 선택했다면 (1) 상어를 먹을 물고기의 위치로 옮겨준다. (2) 이동횟수와 먹은 물고기수를 더해주고 (3) 상어가 레벨업 할 조건을 만족한다면 레벨업! 6. 더 이상 먹을 물고기가 없다면 break -> 전에 한번 도전했다가 실패한 문제이다. 이번 해..

[python] 백준 - 4963. 섬의 개수

문제 해결 1. DFS or BFS를 이용해 몇개의 무리가 있는지 알아내는 문제이다. 2. while문 한 싸이클이 돌 떄마다 한무리를 체크할 수 있다. 3. visit배열을 따로 만들어 사용하거나, 지나온 곳을 다른값으로 바꿔주는 방법을 이용한다. 소스 코드 from _collections import deque while True: w, h = map(int, input().split()) if w == 0 and h == 0: break island = [list(map(int, input().split())) for _ in range(h)] # 상 우상 우 우하 하 좌하 좌 좌상 # 8방향 탐색을 위해 dx = [-1, -1, 0, 1, 1, 1, 0, -1] dy = [0, 1, 1, 1, 0..