민희의 코딩일지

https://www.acmicpc.net/problem/2468 알고리즘BFS 풀이 만만하게 보면 안되는 문제!!!!N은 보드의 너비 (N x N 크기의 보드) 연결요소의 개수를 구하는 문제처렁 평이하게 BFS 코드를 짠다... But, 연결요소의 개수를 구할 때 보드에서 1, 0으로 정점간의 연결을 처리하는 것과 달리height 라는 높이 변수를 주고, height 이상이면 1, 미만이면 0으로 생각하면 편하다.dy = (0, 1, 0, -1)dx = (1, 0, -1, 0)def is_valid_coord(x, y): return 0 height: chk[nx][ny] = True dq.append((nx, ny))  height를 1~..

https://www.acmicpc.net/problem/1697 알고리즘BFS (최단거리 탐색) 풀이 앞서 포스팅한 5014 - 스타트링크와 유사한 문제이다.https://anna-in-workplace.tistory.com/60 G까지 가려면 몇번 시도해야하는지 구하는 문제이다. 최단거리 탐색" data-og-host="anna-in-workplace.tistory.com" data-og-source-url="https://anna-in-workplace.tistory.com/60" data-og-url="https://anna-in-workplace.tistory.com/60" data-og-image="https://scrap.kakaocdn.net/dn/btyAvc/hyWztRwHSI/A001m..

https://www.acmicpc.net/problem/5014 알고리즘BFS (최단거리 탐색) 풀이 F: 전체 건물의 층 수 (정점의 최댓값)S: 시작점G: 목표지점S -> G까지 가려면 몇번 시도해야하는지 구하는 문제이다. 최단거리 탐색이므로 BFS 사용 체크배열에 누적한 값을 저장해둔다. 입력이 10 1 10 2 1 일 때 과정을 설명해보면 1. 큐 = [1],now = 1, 큐 = [] 체크배열 = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0] for nxt in (1+2, 1-1):nxt가 3인 경우 -> 큐 = [3], 체크배열 = [0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0]nxt가 0인 경우 -> 유효 좌표 X  2. 큐 = [3],now = 3, 큐 = []..

https://www.acmicpc.net/problem/2644  알고리즘DFS, BFS  풀이 N: 정점의 개수x, y: 촌수를 계산해야 하는 서로 다른 두 사람의 번호 M: 간선의 종류   같은 연결요소내에 속한 정점의 경우에는 간선의 개수를 세면 되고같은 연결요소가 아니라면 -1을 출력하면 된다.7, 3의 경우에는 7, 2, 1, 3을 거쳐야 하므로 아래 코드에서 횟수는 4가 된다. 자기 자신은 빼야하므로 -1을 해주어 답은 3 이 문제는 출력 과정에서 1번 틀렸는데,처음에는 res = 0 으로 선언해두고, res가 0이라면 -1 출력 아니라면 res 출력으로 짰더니, res가 0이 아닌 경우 -1과 res값 모두가 출력되었다. 그래서 res를 빈 배열로 만들어두고, 배열의 길이가 0인 경우 아닌..

https://www.acmicpc.net/problem/2667  알고리즘DFS, BFS 풀이연결요소의 개수(총 단지수)와 연결요소에 속하는 정점의 개수(단지내 집의 수)를 구하는 문제이다.이중 for 문을 돌려 새롭게 bfs 탐색을 시작할 때, 새로운 연결요소의 시작이라고 판단해 연결요소의 개수에 +1을 해주었다. (코드에서 연결요소의 개수는 ans) bfs 내에 d 라는 변수를 선언해 한 연결요소를 순회할 때, (=새로운 정점으로 이동할 때) +1을 해주었다. 쉽게 말하면 방문 처리를 할 때 +1을 해주었다. dq에 아무값도 없을 때 d를 return 했다.  전체 코드# 단지번호붙이기# 연결요소의 개수(ans), 각 연결요소에 해당하는 개수(res)from collections import deq..

https://www.acmicpc.net/problem/11123 알고리즘DFS, BFS  풀이 전형적인 연결요소의 개수 구하기 문제이다.양: #, 풀: . 을 각각 1, 0으로 생각하고 풀면된다. # 인 경우 시작해서, 방문한 지점은 .로 변경해준다. BFS를 시작할 때마다 새롭게 연결요소가 있다고 판단하였다. 전체 코드 # 양 한마리... 양 두마리...# #: 1, .: 0from collections import dequeT = int(input())for _ in range(T): H, W = map(int, input().split()) board = [list(input()) for _ in range(H)] ans = 0 dy = (1, 0, -1, 0) dx ..

https://www.acmicpc.net/problem/17276 알고리즘구현 풀이크기가 n x n인 2차원 정수 배열 X가 있다. (n은 홀수)X를 45도의 배수만큼 시계방향 혹은 반시계방향으로 돌리려고 한다. X를 시계 방향으로 45° 돌리면 아래와 같은 연산이 동시에 X에 적용되어야 한다. -> 시계방향 45도를 기준으로 연산을 짜고 이 연산을 반복해주면 된다. (시계방향 90도: 45도 연산 2번) 반시계방향은 시계방향 + 8번 연산을 시행해주면 된다. 따라서 각도를 360 + 원래 각도로 설정해주었다.if d  연산 4가지 연산을 시행해주면 된다.1. 주 대각선 -> 가운데 열 2. 가운데 열 -> 부 대각선3. 부 대각선 -> 가운데 행4. 가운데 행 -> 주 대각선 5. 나머지는 원래 보드..

https://www.acmicpc.net/problem/15649 알고리즘백트래킹  풀이  : 순열 1부터 N까지의 자연수 중에서 중복없이 M개를 고른 수열 중복없이 -> 순열 사용 1~N까지 수를 담은 배열을 만든 뒤, 그 배열에서 자연수 M개를 뽑음 from itertools import permutationsN, M = map(int, input().split())arr = []for i in range(N): arr.append(i+1)for combi in permutations(arr, M): for i in combi: print(i, end=" ") print() 그런데..  이 문제는 백트래킹 문제였다...백트래킹 그게 뭔데...백트래킹 그거 어떻게 하는건..