링크: https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어 3번 문제에서 백트래킹 함수의 인자로 현재 숫자를 넘겨서 그 숫자부터 반복문을 돌리면 될 듯 구현 import sys input = sys.stdin.readline def back(cnt): if len(road) == m: for i in road: print(i, end=" ") print() return for i in range(cnt, n): road.append(i+..
링크: https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어 전 N과 M 1, 2번 문제에서 백트래킹 내부 반복문의 조건만 없애주면 될 듯? 구현 import sys input = sys.stdin.readline def back(): if len(road) == m: for i in road: print(i, end=" ") print() return for i in range(n): road.append(i+1) back() road...
링크: https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어 백트래킹을 이용 road배열에 값을 넣으며 백트래킹을 진행하고 road의 길이가 m과 같아질 때 road 출력 백트래킹의 인자는 현재 숫자의 다음 숫자를 인자로 넘겨주어 그 수부터 다시 백트래킹을 진행하게 함 다시 돌아올 때에는 pop을 이용해 road를 다룸 import sys input = sys.stdin.readline def back(cnt): if len(road) =..
링크:https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 아이디어 미리 카메라의 위치를 한 번 돌아 찾아둔다. 그 좌표를 통해 백트래킹을 진행하여 1~5번 카메라의 조건만큼 for문을 돈다. 각 카메라의 조건이 지정된 순간 감시를 했다고 쳤을 때 사각지대의 갯수를 찾는다. 감시를 하는 경우는 상하좌우 #을 뿌리는 함수를 만들고 각 경우의 마다 필요한 함수를 쓴다. 예) 2번 카메라의 1번의 경우 좌측에 #을 뿌리는 함수와 우측에 #을 뿌..
링크: https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 아이디어 백트래킹을 통해 벽을 세우는 경우를 만듦 그 경우에서 2인 위치를 기준으로 bfs를 진행하여 감염이 된 상태를 만듦 이후 안전지대의 개수를 세고 result 값과 비교하여 더 큰 값을 result에 저장. 구현(pypy정답) import sys input = sys.stdin.readline # 백트래킹 def back(wall): if wall == 3: tmp_li = [mat[:] for..
링크: https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어 백트래킹사용 for문을 돌며 숫자를 선택 방문여부를 확인하며 돌고 다시 이전 깊이로 돌아갈 때 방문여부를 되돌려줘야함 M개의 숫자를 고른 경우의 경로는 print해준다. 시간복잡조 중복을 허용하지 않은 경우니 N!이다 -> 가능! 구현 import sys # 백트래킹 구현 def back(): # 경로를 찾았을 때 출력 if len(check) == m: for i in chec..
링크: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아이디어 큐를 이용한 BFS 재귀를 이용한 DFS 방문처리 배열 하나로 두 번 사 구현(틀림) import sys from collections import deque #dfs def dfs(v): dfs_li.append(v) for i in range(n): if m_li[i][0] == v and not check[m_li[i][1]]: check..
링크: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여www.acmicpc.net아이디어바로 보자마자 bfs로도 풀 수 있을 것 같음근데 dfs를 연습하기 위해 dfs를 사용2중 for문을 통해 방문처리를 확인하고 dfs진행dfs는 재귀를 사용각 영역마다 each변수로 크기 표현구현import sys input = sys.stdin.readline n = int(input()) danzi = [list(map(int, input().strip())) for _ in range..
링크: https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 아이디어 배열이 그렇게 크지 않아 적록색약인 경우와 아닌 경우 두 번 bfs를 해도 될 것 같음 방문처리 배열도 만들어서 bfs 진행해보자 첫 bfs함수는 색깔을 인자로 같이 넣어주어 같은 색상끼리 묶어주기 두 번째 bfs함수는 R,G를 같은 색상으로 인식하게 해주면 될듯 (조건문) 두번째 함수 돌릴 때는 방문처리 배열을 재활용하자 1이 방문이 되지 않은 것으로 인지 코드 impor..
