문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 DFS(깊이 우선 탐색)를 사용해 풀었습니다. 양방향 간선이므로 graph의 부모, 자식 노드에 해당하는 공간에 서로를 가중치와 함께 추가합니다. 트리의 지름을 구하는 방법은 다음과 같습니다. 루트 노드로부터 거리가 가장 먼 노드를 구합니다. 구한 노드로부터 거리가 가장 먼 노드까지의 거리를 구합니다. 코드 파이썬 import sys sys.setrecursionli..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 BFS(너비 우선 탐색)를 사용해 풀었습니다. 아기 상어의 위치(baby_shark)를 찾아 해당 위치의 값을 0으로 바꾸고 위치를 저장합니다. BFS 함수 내의 fish 리스트에는 같은 거리 상에 있는 먹을 물고기들을 저장합니다. 상하좌우를 확인하며 0 혹은 같은 크기의 물고기는 지나가고, 아기 상어보다 작은 물고기를 fish 리스트에 추가합니다. 만약 먹을 수 있는 물고기가 ..

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 visited는 앞서 방문한 위치를 체크하여 재방문하지 않도록 하고, 경로 및 이동 거리를 저장합니다. visited를 벽 부수기 전후로 나누어 체크합니다. visited[x][y][0] : 벽 부수기 전 경로 visited[x][y][1] : 벽 부수기 후 경로 이동할 위치의 이동 거리를 현재 위치의 이동 거리에 1을 더해 구합니다. 코드 파이썬 import ..

문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 DFS(깊이 우선 탐색), 백트래킹을 사용해 풀었습니다. check 배열을 사용해 같은 알파벳이 적힌 칸을 두 번 지날 수 없도록 합니다. ord 함수를 사용해 알파벳을 0~25의 값을 가지도록 합니다. 처음엔 딕셔너리를 사용해 알파벳을 체크해줬다. 그런데 계속 시간초과가 떠서 찾아보니 딕셔너리는 시간복잡도가 최소 O(1)에서 최대 O(n)까지 가능하다고 하여 리스트 인덱싱으로 ..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 BFS(너비 우선 탐색)를 사용해 풀었습니다. 6 방향(위, 아래, 상, 우, 하, 좌)을 미리 설정해 줍니다. 익은 토마토(1)의 위치를 모두 큐에 추가합니다. 익은 토마토를 주변으로 6 방향을 확인하며 익지 않은 토마토(0)를 익은 토마토(1)로 바꿔주고 바뀐 토마토 위치를 큐에 추가합니다. 시작 시점에 있던 큐를 모두 수행하면 하루가 지난 것이므로 L에 1을..

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)를 사용해 풀었습니다. ※ 'R'과 'G'를 같은 색상으로 변환 후 탐색하는 방법도 있습니다. 코드 파이썬 import sys from collections import deque input = sys.stdin.readline dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] N = int(input()) bo..