문제 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..

문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 다익스트라 알고리즘을 사용해 풀었습니다. ※ heap에서 꺼낸 비용보다 cost의 비용이 더 작다면 넘어갑니다. (time limit 방지) 코드 파이썬 import sys from heapq import heappush, heappop input = sys.stdin.readline INF = sys.maxsize V, E = map(int, in..

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 [수정 전] 브루트포스 알고리즘을 사용해 풀었습니다. tetrominos에 모든 테트로미노에 대해 왼쪽 위 인덱스(x, y)를 기준으로 더할 값을 저장합니다. 모든 테트로미노를 모든 위치에 대조해보며 더 높은 값을 계속해서 업데이트합니다. [수정 후] 백트래킹을 사용해 풀었습니다. 오른쪽, 왼쪽, 아래로 뻗어가면서 테트로미노(4)가 완성되면 더 높은 값을 비교해 업데이트합니다. L이 1..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 백트래킹을 사용해 풀었습니다. home에 집 위치를, chicken에 치킨집 위치를 저장합니다. DFS를 사용해 M개의 치킨집을 선택해 도시의 치킨 거리를 구합니다. ※ 치킨집은 많을수록 최소 거리에 유리합니다. 코드 파이썬 import sys input = sys.stdin.readline INF = sys.maxsize N, M = map(int, input()..