토마토  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했는데 그러면.. 같은 ..

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

트리 트리란? 회사의 조직도, 가계도와 같이 나무처럼 뻗어나가는 모양의 사이클이 없는 그래프다. 노드 간선 루트 노드: 트리의 맨 꼭대기 부모 노드/자식 노드 리프 노드: 자식이 없는 노드 차수와 깊이 그리고 높이 차수: 특정 노드의 자식 수 깊이: 특정노드로부터 루트노드와 떨어져있는 정도 높이: max깊이 + 1 이진트리 트리의 자식을 2개로 한정하면, 이진트리 배열로 나타내기 좋다. 부모는 i, 왼쪽 자식은 i2, 오른쪽 자식은 i2+1 만약 모든 자식이 꽉 차있지 않다면 배열도 같이 비워줘야한다. 이진트리는 한번 알면 여러모로 편하다.. 자식이 2개로 제한되어 있기 때문에 구현도 좋다… 그러니 확실하게 알아둘 것! 트리의 순회 트리를 탐색하는 순회 방법은 3 가지가 있다. 전위 순회(왼>뿌>오) 중..