문제https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 설명2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 ..

문제https://www.acmicpc.net/problem/11559   풀이1. 자료구조 결정처음에 이차원리스트를 사용해야겠다고 생각했다. 구현중 뿌요가 내려올때 앞,뒤 모두에서 원소 빼고 넣을수 있게 리스트 안에 deque형태로 변경했다.뿌요는 아래로 떨어지는데 열단위 변경보다 행단위변경이 쉬울거라 생각해서 입력받은 리스트를 전치했다. (잘못된 생각이였던듯.........)[deque(['.', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'R', 'R']), deque(['.', '.', '.', '.', '.', '.', '.', '.', 'Y', 'Y', 'R', 'R']), deque(['.', '.', '.', '.', '.', '.', '.', '.',..

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 DFS와 BFS를 이용해서 풀 수 있다. 부모노드 결국 탐색했던 이전노드의 값이다! 탐색을 진행하면서 방문하지 않은 노드를 방문시 visited 리스트에 부모 노드의 값을 업데이트 한다. sol1) BFS import sys from collections import deque def BFS(Graph,start,visited): queue=deque([start]) visited[start]=1 while queue: V = queue.poplef..

문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 DFS로 해결했다. DFS의 return이 True일 경우 total_result를 증가시켜 총 단지수를 구한다. (DFS수행시 상,하,좌,우 값은 return 값을 받지 않고 방문처리 되므로, DFS의 return이 True인 경우는 연결요수 중 가장 첫번째 노드가 방문하는 경우이다.) 각각 DFS수행시 방문처리 할때마다 result값을 증가시켜 단지내 집의 수를 구한다. - globa..

문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 풀이 key : 방문을 True, False로 기록하는 보통의 visited리스트를 각각의 촌수를 넣는 리스트로 변경하여 결과를 출력한다 1. 처음 입력받은 target1(x)을 기준으로 촌수를 저장하는 리스트를 visited로 정의한다. 2. 방문하지 않은 노드를 visited=-1로 초기화한다. 3. 처음 방문시 이전의 촌수에 1을 더하여 업데이트한다. 4. visit..

문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 풀이 BFS, DFS로 모두 해결할 수 있다. sol1) BFS BFS를 한번 수행하면 연결된 모든 노드가 방문처리된다.(visited =True) for문으로 Graph의 모든 노드를 탐색하면서 visited가 False인 경우만 세면서 BFS를 수행하면 연결요소의 개수를 셀 수 있다. import sys from collec..