개발자 퉁이리

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 빨간 구슬의 좌표와 파란 구슬의 좌표를 담을 변수를 설정해준다. 그리고 현재 빨간 구슬의 좌표와 파란 구슬의 좌표를 찾아내어 변수에 저장해주고 큐에 추가한다. 그리고 bfs를 돌려준다. 10번 이상으로 움직였을 시는 멈추고..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 bfs를 돌려서 그림의 총 개수와 가장 넓은 그림을 찾아내면 된다. bfs를 돌릴 때, 내장 count는 그림의 넓이다. 그 값과 기존에 저장된 큰 그림의 넓이와 비교해서 더 큰 값을 max에 저장해준다. 이때 방문을 했는지 안 했는지 알기 위해 visited 리스트..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 먼저 0으로 초기화된 배열을 생성해준다. 그리고 직사각형이 포함된 영역에 대해 1을 더해준다. 그러면 0의 값을 가진 좌표에 대해 bfs를 돌려주면 된다. 마지막으로 결과를 출력해줄때에는 오름차순 정렬을 하여 크기 순으로 차례차례 출력해준다...

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 브루트포스 알고리즘 너비 우선 탐색 ⊙ 문제 접근 과정 1의 좌표를 큐에 넣어준다. 그리고 8방향에 대해 bfs를 돌려준다. 이때 이동거리를 누적하여 더해준다. 마지막에 가장 큰 안전거리 값을 출력해주면 된다. ⊙ 문제 풀이 import sys from collections impor..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr ⊙ 문제 ⊙ 제한사항 ⊙ 입출력 예 ⊙ 입출력 예 설명 ⊙ 문제 접근 과정 방문 여부와 단어 차이로 bfs를 돌려주었다. 먼저 queue에 시작 단어를 넣는다. 그리고 그 단어가 words안에 없다면 바로 0을 리턴해준다. 그렇지만 단어가 words 안에 있다면 words를 탐색하여 단어가 하나만 다르고 방문한 적 없는..

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번이..