Backjoon

[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] 백준 - 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..

[python] 백준 - 2606. 바이러스

문제 해결 1. 플로이드와샬 알고리즘 - 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 2. 라고 되어있지만 사실 잘 모르겠고, 이어져있는 정점들을 모두 찾는 문제이다. 3. 인접리스트를 만들고, BFS로 이어져있는 모든 정점을 찾으면 해결되는 간단한 문제! 소스 코드 from _collections import deque def bfs(vertex): # 속도가 빠른 디큐를 사용해서 BFS 탐색 q = deque() q.append(vertex) # 시작점 방문 체크를 True로 해준다음 visit[vertex] = True while q: # 큐에 쌓인 노드들 중에서 하나를 꺼내고 current = q.popleft() # 노드에 인접한 이웃들중 for neighbor in adj[current]..

[python] 백준 - 15683. 감시

문제 해결 완전탐색 시뮬레이션 1. 먼저 CCTV의 위차와 방향들을 따로 리스트에 저장해둔다 2. 각각의 CCTV마다 감시할 수 있는 방향들이 다르기 때문에 하드코딩이지만 방향을 다 설정해준다. (1) 여기서 5번 CCTV는 방향을 바꿀수 없기 때문에 처음부터 탐색할 수 있는 곳들을 모두 표기해준다. 3. DFS를 통해 모든 경우의 수를 계산해 준다. 4. 경우의 수를 하나 찾을 때마다 감시하는 영역을 표시해주어 사각지대가 최소인 부분을 찾는다. -> 뭔가 하드코딩한 것 같지만 시뮬레이션문제라 어쩔 수없는 것같다. 시뮬레이션 문제를 풀면 진이 빠지는 것 같다. 항상 너무 길다...😵 소스 코드 from copy import deepcopy def dfs(idx, maps): # idx : 몇 번째 cct..