시나위

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 1번 노드에서 가장 멀리 떨어진 노드 찾기 접근 1. 그래프 탐색 BFS로 탐색하면 1에서부터 각 노드마다의 거리가 나온다. 가장 마지막 구해진 거리(가장 먼 거리)와 같은 개수를 구하면 된다. max_dist = max(max_dist, visit[adj]); 모든 노드를 탐색할때 가장 큰 값을 저장해놓고 int ret = 0; for (auto v:visit) { if (v == max_dist) ret++; } return ret; 해당 값을 사용해서 같은 거리인 노드의 개수를 센다. 전체 코..

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 요약 트리의 지름 출력 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것 접근 1. 생각의 흐름 그래프 탐색 두번으로 진행하면 될 것 같다. 아무 점에서 시작해서 가장 먼 지점까지 탐색한다. 첫번째 탐색이 끝나면 가장 먼지점에서 두번째 탐색을 시작한다. // 1. 아무 노드에서 시작해서 가장 먼노드까지 간 다음, pair tmp; tmp = bfs({1, 0}); // 2. 가장 먼노드 노드에서 가장 먼노드까지 탐색 tmp = bfs({t..

https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 그래프탐색이 가미된 시뮬레이션 문제이고, 알고리즘 순서는 다음과 같다. 1. 입력 2. 시뮬레이션 (k번) 2-1. 주사위 이동 2-2. 점수 획득: 그래프 탐색 2-3. 다음 이동방향 결정 3. 출력 주사위 이동을 할때 주사위의 위치를 변경하면서 주사위 면도 변경했다. 주사위의 첫 면이 1 2 3 4 5 6 이라 하고 top이 1 bottom이 6이라고 할때 동쪽으로 굴러가면 ..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 그래프 탐색을 사용한 시뮬레이션 문제이다. 시뮬레이션 순서는 다음과 같다. 1. 이차원 배열에서 아래에서 부터 그래프 탐색으로 4칸 이상의 지점 찾기 -> 있으면 제거 2. 제거된 값이 있으면 중력 적용후 1,2 반복, 없으면 반복 중단 import sys; input = sys.stdin.readline from collections import deque d = [(0..

https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 그래프 탐색 문제이다. 문제를 풀기 전 다음 순서로 구현하려고 했다. 1. 입력 우선 방 개수와 크기를 알아야하므로 방의 개수를 저장하는 변수(num_room)와 각 방 크기를 저장하는 리스트(room_size)를 만들었다. 그리고 visit 배열을 만들어서 방문한 점인지 파악했다. 2. 그래프(이차원 배열) 탐색 2-1. 방 개수와 크기 확인 모든 자리를 순회하면서 BFS를 진행했다. 방문..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백트래킹과 그래프 탐색 알고리즘을 모두 사용해야하는 문제이다 3개의 벽을 설치할 땐 백트래킹을 설치한 이후 바이러스가 전파되는 것은 그래프 탐색(BFS를 사용했다)을 하면된다. 바이러스 전파가 끝나면 이차원 배열에서 안전한 구역을 찾으면 된다. # import sys; input = sys.stdin.readline from collections import deque def bfs(): global N, M..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS로 진행했다. #include #include #include using namespace std; #define D(s) ((2 * (s)) % 10000) #define S(s) (((s) + 9999) % 10000) #define L(s) (((s) % 1000) * 10 + ((s) / 1000)) #define R(s) (((s) / 10) + (((s) % 10) *..

https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 그래프 탐색을 활용하는 문제이다. BFS 로 이차원배열을 탐색했고 해당 구역에서 양과 늑대의 수를 확인한다음 한쪽 값만 내보내는 방식으로 진행했다. # import sys; input = sys.stdin.readline from collections import deque def bfs(i, j, _map, visit): global n, m ret = [0, 0] q = deque..

https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구슬탈출 2와 같은 문제이고 최소 거리일때의 경로까지 같이 출력해야한다. 구현한 알고리즘은 다음과 같다. 1) 입력을 받으면서 R, B, O의 위치를 저장한다. 2) BFS를 사용해서 시뮬레이션을 돌린다. 2-1) 먼저 움직이는 구슬을 찾는다. 2-2) 움직인다. 2-3) 파란 구슬이 빠진 경우 다음 방향을 탐색한다.(continue) 2-4) 빨..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net import sys; input = sys.stdin.readline from collections import deque def search(start, size, board): d = [(-1, 0), (0, -1), (0, 1), (1, 0)] ret = [] visit = [[-1 for _ in range(N)] for _ in range(N)] visit[start[0]][sta..