개발자 퉁이리

https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 비트마스킹 ⊙ 문제 접근 과정 11 & 1 = 1011 & 0001 = 0001 11 & 2 = 1011 & 0010 = 0010 11 & 4 = 1011 & 0100 = 0000 11 & 8 = 1011 & 1000 = 1000 위 코드가 핵심 코드다. 모든 값이 0이라면 벽으로 안 막혀 ..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 다익스트라 0-1 너비 우선 탐색 ⊙ 문제 접근 과정 방문 여부를 카운트로 하여 방문 시에 +1을 count up 해주었다. 만약 순간이동 하는 경우는 방문 카운트를 건드리지 않는다. 왜냐하면 순간이동에 걸리는 시간은 0초이기 때문이다. 그리고 순간이동의 경우에는..

https://www.acmicpc.net/problem/1325

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 브루트포스 알고리즘 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 bfs코드를 먼저 짜준다. 그다음 rain이라는 변수를 설정해 입력받은 배열에서 가장 큰 높이까지 한 바퀴를 돌 때마다 값을 하나씩 올려준다. 그러다가 그 값이 가장 큰 높이까지 도달하면 bfs로 조사한 안전한 지역 중 최대를 출력해주면 된다. ⊙ ..

https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 윌리암슨수액빨이딱따구리 식구는 식사를 하고 싶어 하는데 귀찮아서 가장 가까운 곳을 가고 싶어 하는 간단한 문제다. 1은 벽, 0은 통로이고 윌리암슨수액빨이딱따구리 식구는 2번이..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 bfs를 돌렸다. 2번. 한 번은 입력받은 RGB 그대로 돌려서 구역을 찾아냈다. 마지막 한번은 R을 전부 G로 바꾸고 visited 여부를 초기화해준 후 돌려줬다. ⊙ 문제 풀이 import sys from collections import deque ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 브루트포스 알고리즘 너비 우선 탐색 ⊙ 문제 접근 과정 재귀를 통해 벽을 세우고 3개를 다 세웠으면 그때 bfs를 돌린다. bfs는 바이러스를 기준으로 퍼져나가게 코드를 짜주었고, count 함수를 사용하여 0의 개수를 출력해준다. 0은 안전지역이다. 안전지역이 가장 많은 값을 ans에 저장해 주어 브루트 포스, 모든 경우에..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 자료 구조 우선순위 큐 위상 정렬 ⊙ 문제 접근 과정 기존의 위상 정렬에 플러스 알파가 필요했다. 그 플러스 알파는 추가되는 큐에 대해 오름차순 정렬로 입력해줘야한다. 위상 정렬의 특징 중 하나, 위상 정렬에서는 여러 가지 답이 존재할 수 있다. 이 문제에서는 아니다. 가장 난이도가 쉬운 순서대..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 위상 정렬 ⊙ 문제 접근 과정 위상 정렬 알고리즘 문제다. 위상 정렬 알고리즘은 큐를 이용하여 풀 수 있다. 큐를 이용하여 위상 정렬 알고리즘을 푸는 과정은 1️⃣ 진입 차수가 0인 모든 노드를 큐에 넣는다. 2️⃣ 큐가 빌 때까지 while문을 돌린다!! 3️⃣ 반복문에서는 큐에서..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 깊이 우선 탐색 백트래킹 ⊙ 문제 접근 과정 bfs를 사용해 문제를 풀었다. 조건을 통해 알파벳이 탐색하지 않았고 범위 안에 있다면 탐색을 추가한다. 계속해서 반복하여 answer의 최댓값을 갱신해준다. 처음에 dfs로 문제를 풀어봤는데 pypy로 해도 시간 초과가 나서 bfs로 풀었다. ⊙ 문제 풀이 i..