알파벳오랜만의 백준 포스팅!!코테에서 부족함을 절실히x99 느끼고 다시 알고리즘을 본격적으로 시작했다..🥲🤗 문제 바로 가기  알고리즘 말이 보드를 탐색하는 조건은 다음과 같다.① (1,1)부터 탐색한다.② 지금까지 지나온 모든 칸에 적혀있는 알파벳과 달라야 이동할 수 있다. 이 조건 아래에서 가능한 경로 중 최대한 큰 수를 구하는 것이 목표다.따라서, DFS를 통해 탐색하는 방법을 선택했다.  def dfs(y,x,cnt): visited[y][x] = True alphabet[ord(graph[y][x])-65] = True # print('시작점: ', graph[y][x]) # 현재 위치에서 네 방향의 위치 확인 for dy, dx in dr: ny, nx..

1068 트리 1068번: 트리첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다www.acmicpc.net  알고리즘1. 이 문제는 부모가 인덱스, 해당 인덱스의 자식을 리스트로 부여한다. # index: 부모, 값: 자식# 노드의 범위가 0 ~ n-1인 경우for i in range(n): # root인 경우 if tree[i] == -1 : continue else: graph[tree[i]].append(i) 이렇게 표현하는 이유는 DFS 탐색 구현을 좀 더 직관적으로 평소와 같이 할 수 있기 때문이다...

바이러스 Baekjoon Online JudgeBaekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.www.acmicpc.net  알고리즘입력에서 직접 연결되어 있는 쌍이 주어진다.더보기더보기1 22 31 55 25 64 7 1번 노드는 2번 노드와, 2번 노드는 3번 노드와 1번 노드는 5번 노드와 ∙∙∙ 연결되어있다는 뜻이다.이렇게 정의하는 그래프를 양방향 그래프라고 하고, 다음과 같이 코드로 구현할 수 있다. 양방향 그래프를 2차원 리스트로 정의graph = [[] for _ in range(n+1)]for _ in range(m): x,y=map(int, input().split()) graph[x].append(y) graph[y].append..

토마토  7576번: 토마토첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토www.acmicpc.net 알고리즘 일반적인 그래프 탐색과 달리, 입력된 초기 그래프에서 1이 있는 곳을 동시에 인접 지역을 탐색해야 한다. 즉, 시작점이 여러 개다.시작점을 미리 queue에 넣어서 방문할 수 있도록 한다.1이 있는 지점을 방문하면서 인접 장소를 탐색한다. 이때 익지 않은 토마토가 있다면 방문하고, 몇 번째 날짜인지 기록한다.이 부분을 print로 찍어보면 다음과 같이 나온다.일단 queue에 익은 토마토(1)의 위치를 모두 append 해두었으므로..

1743 음식물 피하기   알고리즘cnt 처리방식 구현이 쉽게 떠오르지 않았다.  def dfs(x,y) : cnt = 1 visited[x][y] = True for dx, dy in d : nx, ny = x+dx, y+dy # 여기가 연결되는 부분이니까 cnt += 1 처리를 해주고, if 0  이 문제에서 dfs 함수는 #를 발견하면 주변(d 좌표)을 탐색하면서 같은 영역에 속하는 곳의 크기가 얼마인지 세어주는 함수이다. 따라서 if문 조건은 주변 영역에서 계속 #이 이어지는 경우이므로, 이때 개수를 세어주어야 한다. 처음에 잘 생각이 안나서 cnt += 1 이런식으로 세어주고 return했는데 그러면.. 같은 ..

BFS와 최단 경로BFS는 최단거리와 관련있다. 왤까?BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다.bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다.그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다.흠.. 이렇게만 봐서는 왜 최단경로인지 모르겠다;; 예시를 보자.시작점 A에서 F까지의 최단경로를 알아본다고 했을..

알고리즘아래와 같이 그래프의 연결 상태가 주어진다면, 인접 리스트와 인접 행렬 두 가지 방식으로 관계를 정의할 수 있다.이 문제에서는 인접 리스트를 사용하여 그래프 관계를 정의하겠다.1 21 31 42 43 4 [인접리스트를 활용한 그래프 표현] 1. 간선의 개수 만큼 정점의 관계들이 입력 되니까 간선의 수 만큼 for문을 반복.2. 두 정점을 입력 받아서 연결관계를 표현하기 위해 서로의 리스트에 저장. 이때 정점의 정보는 1 ~ n까지의 숫자로 나타나므로, graph의 크기를 n+1만큼 해주어야 한다.(range 함수는 n-1까지의 수를 반환하니까)# 그래프 초기화graph = [[] for _ in range(n+1)]# 간선의 개수가 m일 때for _ in range(m) : x, y = map(..

https://www.acmicpc.net/problem/3184 3184번: 양첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다.www.acmicpc.net알고리즘그래프 탐색 문제인 건 알겠는데, 같은 영역을 어떻게 판단하지?가 고민이었다.적록색약 문제에서는 bfs 함수에서 같은 색을 만나면 계속해서 q에 그 지점을 삽입하면서 탐색을 하게 만들었는데,얘도 마찬가지다..! 그래서  ⭐️⭐️⭐️⭐️⭐️ bfs 함수의 q가 모두 끝나면 ⭐️한 영역⭐️에 대한 큐가 끝나는 것임..⭐️⭐️⭐️⭐️⭐️그니까 while q 이 부분이 주변을 탐색하는 핵심..

https://www.acmicpc.net/problem/10026 10026번: 적록색약적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)www.acmicpc.net이 문제는 조금 개인적인 일화가 있는데,, 작년 2학기에 교내 알고리즘 대회를 준비하면서 이 문제를 접하고 엄청 허둥지둥 거리다가 포기한 기억이 있다. 이 문제 구현을 어떻게 할지 구상해보면서 문득 저번 학기가 떠올랐는데, 방학 동안 꾸준히 공부한 보람이 조금이나마 있어서 다행이다..!   알고리즘bfs, dfs는 알고리즘이 정해져 있어서 막 구현이 어려운 문제는 아니다.하지만 이 문제를 어떻게..

dfs : 최대한 깊게 방문하지 않은 노드들에 쭉 방문하다가, 더이상 진행할 수 있는 인접정점이 없으면 되돌아감 - 재귀bfs : 한 노드에서 인접노드까지 방문한 적이 없는 모든 노드를 queue에 삽입. que는 FIFO 방식이라서 순차적인 구현 DFSfrom collections import dequer,c = map(int, input().split())pasture = [list(input()) for _ in range(r)]visit = [[0]*c for _ in range(r)]d = [(0,1),(0,-1),(1,0),(-1,0)]cnt = 0def dfs(x, y) : visit[x][y] = 1 for dx, dy in d : nx,ny = x+dx, y+d..

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로www.acmicpc.net 분할(partition)분할은 말 그대로 여러 개로 나눈다는 뜻인데, 이산수학에서의 분할은 보통 집합의 분할을 뜻한다.집합의 분할이란 공집합이 아닌 집합 X를 서로소인 부분집합 Y1, Y2..로 나누는 것이다.집합 Y들을 모으면 집합 X가 된다.X의 원소들은 서로소이며, 교집합이 없다.이 문제에서는 각각 일(day)별로 원소들이 있고 이들을 M번 분할하여 최소 K를 찾는다.입력 예제를 분할의 예로 들면 1..