아이테킨의 끄적끄적

빠트리지 않고 탐색하는 것과 이미 탐색했던 조합은 Pass할 수 있도록 알고리즘을 짜야 한다. 마지막으로 물통사이를 왔다갔다할 때 물이 넘치는지 모자라는지 체크하고 문제에서 요구한 조건(A의 통이 비어있을때)에 부합할때 C통에 남아있는 물을 저장해두면 된다. 참고 : https://pacific-ocean.tistory.com/392 # 2251번: 물통 a,b,c = map(int,input().split()) ans = [] from collections import deque q = deque() q.append([0,0,c]) check = [[0] * 201 for i in range(201)] ans = [0 for i in range(201)] def bfs(): while q: x,y,z ..

bfs탐색 알고리즘을 통해서 풀 수 있는 문제다. 이 문제에서 신경써야 하는 부분은 보통은 상하좌우만 탐색을 하는 문제가 많았는데 이번 문제는 대각선까지 탐색을 해야 한다. # 4963번: 섬의 개수 # 상하좌우대각선까지 dx = [0,0,-1,1,1,1,-1,-1] dy = [1,-1,0,0,1,-1,1,-1] from collections import deque def bfs(w,h): cnt = 0 for x in range(h): for y in range(w): if graph[x][y] == 1: cnt += 1 q = deque() q.append([x,y]) while q: a,b = q.popleft() for i in range(8): nx = a + dx[i] ny = b + dy[i..

2가지 알고리즘을 이용하여 풀 수 있다. 1. BFS 2. bruteforce 첫번째로 BFS알고리즘은 주어진 그래프에서 탐색을 하기 위한것이므로 BFS문제를 많이 풀어본 사람이라면 쉽게 풀 수 있을것이다. 두번째로 이 문제에서 bruteforce는 벽을 세울 때 사용한다. 문제에서 입력값의 범위가 크지 않으므로 모든 범위를 계산해서 제일 큰 값을 고르면 된다. 참고로 제출할 때 python3이 아닌 pypy3로 제출해야 통과된다. python은 시간초과가 뜬다. 왜 이렇게 다른지는 나중에 ㅠㅠ 아이디어를 코드로 구현하는 것과 여러가지 환경설정에 대해서 알아야 할 부분도 많다 ㅠㅠ 가야할 길이 많지만 차근차근 꾸준히 걸어가자! # 14502번: 연구소 from collections import deque..

최단거리를 찾는 문제이므로 bfs탐색 알고리즘을 사용하면 쉽게 풀수 있다. 또 시간초과가 떳다. 이게 시간초과가 뜬 내가 만든 코드이고 from collections import deque import sys input = sys.stdin.readline def bfs(): while queue: x,y = queue.popleft() for step in range(8): nx,ny = x + dx[step], y+dy[step] if 0

이 코드로 했더니 테스트케이스의 답들은 잘 나오는데 시간초과가 떠버렸다. 3차원 배열을 사용해야 하는 문제라서 반복문 3개를 썻다고 시간초과가 나오는 건 아닐거라고 생각한다. 확실한 이유는 아닐 수도 있지만 내 생각에 중간에 zip내장함수를 이용해서 좌표를 만들어낼때 내부적으로 연산이 더 되는게 아닌가 싶다. 사실 잘 모르겠다. 어떤 부분에서 시간 초과가 나는지...ㅠㅠ # 7569 토마토 3차원 문제 import sys input = sys.stdin.readline m,n,h = map(int,input().split()) graph = [[] for _ in range(h)] for i in range(h): for _ in range(n): graph[i].append(list(map(int,in..

최단거리를 묻는 문제에서는 우선 BFS탐색법을 생각해봐야 한다. 단순히 최단거리를 묻는 문제가 아니라 여러가지 조건들을 만족시켜야 하는 상황이어서 코드가 약간 길어지긴 했지만 다행히 통과가 되었다. BFS문제는 큐 자료구조를 이용해서 큐가 빌때까지 하나씩 노드를 뽑아서 탐색하는 방법이다 1. 큐 자료구조를 만들고 2. 큐에서 한개씩 뽑아서 탐색 3. 큐가 빌때까지(while queue:) 코드 # 7576 토마토 m,n = map(int,input().split()) graph = [] for _ in range(n): graph.append(list(map(int,input().split()))) arrow = [[-1,0],[1,0],[0,-1],[0,1]] # 상하좌우 from collections..

bfs문제다. 최단거리를 찾는 문제는 bfs탐색법을 활용하면 된다. bfs는 큐 자료구조를 활용하는데 큐에서 한개씩 꺼내서 연결된 노드들을 탐색하면서 큐가 빌때까지 루프를 돌려주면 되는 탐색 알고리즘이다. # 2178 미로 탐색 - 최단거리 n,m = map(int,input().split()) graph = [] for _ in range(n): graph.append(list(map(int,input()))) arrow = [[-1,0],[1,0],[0,-1],[0,1]] # 상하좌우 from collections import deque def bfs(x,y,step=1): q = deque() q.append([x,y]) while q: node = q.popleft() for i in arrow:..

이번 문제는 이전 단지번호 붙이기(2667번)에서 사용되었던 방법을 이용하면 풀수 있다. 아니, 문제 자체는 오히려 더 쉽다. 하지만 이번 문제에서도 에러를 만나게 되었는데 바로 런타임에러(recursion error)이다. 이놈을 만나고 나서 계속 코드를 하나하나 뜯어보았다. 분명히 코드엔 잘못된 부분이 없는것 같다. base case조건도 분명하게 걸어놨고 테스트 입력값에서도 잘 돌아갔다. 구글링을 통해서 찾아보니 재귀의 깊이제한을 설정해줘야 한다는 것을 알았다. 파이썬은 기본 재귀 깊이 제한이 1000으로 매우 얕다고 한다. 따라서 재귀를 사용하여 문제를 풀 때에는 위의 코드를 넣어주어 재귀에러가 나는것을 막아주어야 한다. 이후에 코딩테스트에서도 이부분은 필수라고도 적혀있으니 기왕이면 외워두는게 좋..

dfs/bfs문제다. 문제를 크게 꼬거나 어렵게 만들지 않은 것 같다. dfs/bfs 둘중에 하나만 제대로 구현할 줄 알면 풀 수 있는 문제인 것 같다. 감염된 컴퓨터의 개수를 구하는 문제이므로 탐색문제에서는 시작점으로부터 방문한적이 있는 노드의 수를 카운팅하면 되는 문제이다. BFS를 이용한 풀이 # 2606번 바이러스 - bfs n = int(input()) m = int(input()) graph = [[0]*(n+1) for _ in range(n+1)] for _ in range(m): a,b = map(int,input().split()) graph[a][b] = graph[b][a] = 1 visited = [0]*(n+1) from collections import deque def bfs..

가장 기본적이고 DFS/BFS 개념문제라고 생각한다. DFS는 깊이우선탐색이라고 하여 그래프 자료구조를 그려놓고 수직의 방향으로 먼저 탐색하는 방법을 말한다. 재귀 혹은 스택 자료구조를 이용하여서 구현할 수 있다. BFS는 넓이우선탐색이라고 하여 그래프에서 수평방향으로 먼저 탐색하는 방법이라고 이해하면 될것 같다. 큐 자료구조를 이용하여 구현한다. # 1260번 # 입력값을 받는 부분 # 인접행렬로 그래프를 표현하였다. n,m,v = map(int,input().split()) graph = [[0]*(n+1) for _ in range(n+1)] for i in range(n+1): a,b = map(int,input().split()) graph[a][b] = graph[b][a] = 1 # DFS구..