DecordRay

문제 : https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 풀이 : 두가지 방법(BFS, DFS)으로 풀이를 진행하였음 첫번째 방법(BFS) 1. 노드 저장할 graph 리스트 초기화 2. 방문 여부 판별 + 몇촌인지 저장할 visited 리스트 초기화 3. graph에 노드 저장 4. bfs 진행 5. 정답 출력 visited[target2]가 0일 경우 촌수 확인 할 수 없는 경우이므로 -1 출력 visited[target..

문제 : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 : DFS방법 밖에 떠오르지 않아서 DFS방법으로만 풀이하였음 첫번째 풀이 당시 10번이 넘는 시도동안 시간초과가 났고, 이를 해결하지 못하여 다른 사람의 풀이를 참고하여 수정하였음 첫번째 방법(시간초과) 1. max_count(몇 칸을 갔는지 저장하기 위한 2차원 리스트) 생성 2. visited(방문여부를 확인하기 위한 2차원 리스트) 생성 3. chk_Alpha(사용한 ..

문제 : https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 : 1. 트리상에 연결되어 있는 정점들을 입력받을 graph 리스트 생성 2. 각 노드들의 부모노드를 저장할 parent 리스트 생성 3. 간선의 방향이 정해져 있지 않기 때문에 graph[a].append(b) graph[b].append(a) 와 같이 입력받은 노드들을 저장해줌 4. bfs알고리즘을 통해 정점마다 들어있는 노드들을 순회하면서 parent값이 0이면(아직 parent값이 안들어간 것이므로) parent값(v)을 넣어줌 5. pa..

문제 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 : 1. 1부터 100이하의 높이마다 각 안전 영역의 개수를 세주어야 하므로 find_safety함수를 만들기로 함 find_safety(h) 함수는 안전 지역 -> 1 물에 잠기는 지역 -> 0 으로 그래프를 변경해주는 함수 2. 이후 높이를 1씩 증가시켜가면서 bfs 진행을 통해 높이에 따른 안전영역의 개수를 파악 + 추가적으로 백준 14502 연구소 문제도 이와 비슷하니 한번 풀어보는..

문제 : https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 : 1. 그래프 탐색 문제라고 생각하여 BFS 풀이법을 사용하기로 생각. 2. 기존 알고리즘 문제의 경우와 달리 y축이 뒤바뀌어 있기때문에 이부분을 원래 풀던 방식으로 변경하고자 (M-y2, M-y1)으로 코드 작성 3. 직사각형이 그려진 부분을 1 값으로 저장 -> graph[j][k] = 1 4. bfs 구현 -> 상 하 좌 우로 이동하면서 빈 영역의 개수를 ..