15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제다. 이번에는 1부터 N까지 자연수 중 중복없이 M개를 고르지만, 고른 수열은 오름차순이어야 한다는 조건이 있다. # 15650번: N과 M(2) n, m = map(int, input().split()) result = [] def backTracking(num, x): if num == m: print(" ".join(map(str, result))) return for i in range(x+1, n+1): if i not in result: ..
파이썬
15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제다. 이 문제는 2가지 방식으로 풀 수 있다. # 15649번: N과 M(1) n, m = map(int, input().split()) result = [] visited = [False] * (n+1) def backTracking(num): if num == m: print(" ".join(map(str, result))) return for i in range(1, n+1): if not visited[i]: visited[i] = True ..
14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 단순 구현 문제다. 주어진 조건을 잘 구현하면 되는 문제 # 14503번: 로봇 청소기 import sys input = sys.stdin.readline n, m = map(int, input().split()) # 방의 크기 r, c, d = map(int, input().split()) # 로봇 초기 위치, 바라보는 방향(0 ~ 3 -> 북, 동, 남, 서) graph = [list(map(int, input..
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 전형적인 DFS/BFS 탐색 문제다. 물의 높이에 따라 안전 영역의 개수가 달라지게 되는데, 안전 영역 개수의 최댓값을 출력하면 되는 문제. 나는 DFS로 구현했다. # 2468번: 안전 영역 import sys sys.setrecursionlimit(10**9) # 재귀 범위 조절 n = int(input()) # 행, 열 개수 graph = [] max_height= 0 # graph에서 제일 높이가 높은 지역의 높이 for _ in range(n): data = ..
5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 전형적인 BFS문제다. 이 문제는 2차원 리스트도 아니고, 1차원 리스트를 활용하므로 더 쉬운 문제다. # 5014번: 스타트링크 from collections import deque import sys input = sys.stdin.readline f, s, g, u, d = map(int, input().split()) building = [-1] * (f+2) # 건물의 층 수(방문하지 않은 경우 -1) building[s] = 0 # 시작점까지 누른 버튼의 수는 0..
7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 전형적인 BFS 문제다. 단, 이 문제에서 일반적인 BFS 문제와 다른 점은 3차원 리스트라는 점이다. 3차원 리스트긴 하지만 개념은 동일하기에, 큐 자료구조를 활용해 BFS를 구현했다. # 7569번: 토마토 from collections import deque import sys input = sys.stdin.readline m, n, h = map(int, input().split()) box = [] # box를 저장하는 리스트 ..
46_아기 상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기 happenundo.tistory.com
16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS를 활용한 구현 문제. 풀이 코드 from collections import deque INF = int(1e9) # 무한(10억) # 맵의 크기 N 입력 n = int(input()) # 전체 모든 칸에 대한 정보 입력 array = [] for i in range(n): array.append(list(map(int, input().split()))) # 아기 상어의 현재 크기 변수와 현재 위치 변수 now_size = 2 now_x, now_y ..
45_최종 순위 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인 happenundo.tistory.com
3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상 정렬 문제다. 문제에서는 작년 순위와 상대적으로 순위가 바뀐 팀들의 목록이 주어졌을 때, 올해 순위를 만들 것을 요구한다. 즉, 정해진 우선순위에 맞게 전체 팀들의 순서를 나열해야 한다는 점에서 위상 정렬 알고리즘을 떠올릴 수 있어야 한다. 예를 들어 순위가 5 4 3 2 1 순으로 주어진다면 5 -> 4, 3, 2, 1 4 -> 3, 2, 1 3 -> 2, 1 2 -> 1 을 가리키도록 그래프를 만든다. (여기서 이렇게 그래프를 만들었으면 바로 풀..
