시작이 반

2차원 리스트에서 로봇 청소기가 청소하는 구역을 구하는 문제 구현, 시뮬레이션 문제인데 맵 이동 문제는 보통 DFS, BFS로 푸는데 어떻게 풀어야 할지 몰라서 일단 생각나는데로 풀었다. 내일 DFS로도 풀어본다. 리스트 탐색문제는 dx, dy로 보통 푸는것 같다. 풀이 시작 위치를 방문(청소)을 했다고 지정해준후 함수를 시작시킨다. 무한루프를 사용 - 현재 방향의 왼쪽의 좌표를 구한다 - 구한 좌표가 방문(청소)를 하지 않고 벽이 아닐경우 - 현재 좌표를 구한 좌표로 바꿔준다. 방향도 현재방향의 왼쪽으로 바꿔주고 (ex. 현재 방향이 북(0)이면 서(3)) 방문(청소)처리하고 카운트 증가. - 벽이거나, 방문(청소)한곳이면 - 방향만 바꿈, 턴 횟수 증가 - 턴 횟수가 4일때 후진, 후진할수 없을경우 ..

7576번 2차원 토마토 문제와 같은 문제이다. 3차원 배열은 [z][x][y]인 것을 기억하자 또한 3차원 배열에서 Max값을 얻기 위해 쉽게 얻는 방법이 있는지 확인할려고 검색을 해본결과 2차원 배열에서 max(map(max, graph)) 이런식으로 하면 나온다고 하여 응용을 해서 max(map(max, max(graph)))를 사용하였는데 틀렸다고 나왔다. map사용법을 아직 잘모름... 3중포문을 사용하여 Max값을 구함 from collections import deque import sys input = sys.stdin.readline col, row, h = map(int, input().split()) graph = [[list(map(int, input().split())) for _..

미로 문제와 동일한 문제이다. 하지만 익은 토마토가 여러개 있을경우 그 토마토에 대해서 bfs처리를 동시에 해줘야한다. 처음에는 만약에 익은토마토가 여러개이고 안익은 토마토로 연결되어있으면 익은토마토의 개수만큼 나눠주면 되지아 않을까하고 풀어봤는데 아니었다. 어떻게 동시에 bfs를 돌려야 하는지 고민하는데 쓰레드 밖에 도저히 생각이 나지 않아서 알아본결과 큐에 익은 토마토를 넣어주면 되는 것이었다. 간단한 방법이었지만 생각이 나지 않으면 풀 수 없는 문제.. bfs에서 큐를 왜사용하는지 알아야함 from collections import deque import sys input = sys.stdin.readline col, row = map(int, input().split()) graph = [list..

DFS 와 BFS 언제 사용? 보통 문제들을 보면 DFS와 BFS를 둘 다 사용하여 풀 수 있다. (모든 정점들을 탐색하는 알고리즘) BFS는 최단경로 문제, 가중치 없는 그래프 문제에 적합하다. (미로 같은 문제) DFS는 경로의 특징을 저장해야 하는 문제에 적합하다. 가중치 관리가 용이하고 탐색에 대한 제약 조건이 있는 문제 위상정렬에도 DFS를 사용한다고 한다. DFS출력값의 역순은 위상정렬의 결과와 같다. 참고 - devuna.tistory.com/32 - ssssum.tistory.com/3

미로 문제 즉, 최단거리 문제는 BFS를 사용하여 해결할 수 있다. 현재 위치에서 가장 가까운 점을 먼저 방문하기 때문이다. BFS BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 시작 좌표(0,0)를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 좌표를 꺼내 해당 좌표의 인접 좌표(상, 하, 좌, 우)중 방문하지 않고, 해당 좌표의 값이 0이 아닌 경우 좌표를 모두 큐에 삽입하고 방문처리를 한다. 해당 좌표의 값을 이전 좌표의 값 +1 로 증가 시킨다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 답 : n, m의 좌표에 있는 값 (해당 풀이에선 0부터 시작함으로 n-1, m-1이다.) import sys from collections import deque input = sys.s..

배추흰 지렁이가 인접한(상, 하, 좌, 우) 배추를 보호 한다고 한다. 즉, 이 문제는 배추의 영역을 구하는 문제이다. DFS, BFS둘다 사용 할 수 있지만 DFS의 경우 재귀의 횟수에 따라 메모리, 시간초과가 뜰 수 있다. 이때 sys.setrecursionlimit(n) 을 사용하여 제귀횟수를 제한할 수 있지만 BFS를 사용하는 것이 좋아보인다. 여기서 노드는 배열의 좌표라고 생각한다. DFS 시작 노드에서 인접한 노드 선택하여 방문처리를 하고 탐색을 들어간다. 더이상 탐색할 노드가 없으면 이전노드에 연결되어 있는 점들 중 방문하지 않고 다음으로 큰 노드을 탐색한다. BFS BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내..

처음에 DFS로 풀었지만 메모리 초과가 나왔다. 재귀에 이상이 있음을 확인하였다. 입력크기가 n(1 ≤ n ≤ 500), m(1 ≤ m ≤ 500) 이기 떄문에 재귀로 풀면 메모리 초과가 뜬다. 때문에 BFS를 사용하여 풀었다. BFS (2차원배열 인접 리스트 확인 (상, 하, 좌, 우)) dx, dy를 이용하여 상, 하, 좌, 우 확인 for 문을 이용하여 2차원 배열의 모든 좌표 확인 1. 방문하지 않고, 배열의 값이 1일 경우 큐에 삽입하고 방문 처리를한다. 2. 큐에서 해당 좌표를 꺼내 그 좌표의 상, 하, 좌, 우를 확인한다. 상, 하, 좌, 우에 1이 있고 방문하지 않았다면 큐에 삽입후 방문처리를한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. (큐가 빌때까지) from c..

먼저 2차원 배열을 생성할 수 있어야한다. graph = [list(map(int, input())) for _ in range(n)] 입력을 받으면서 그래프를 만든다. 그래프의 1의 묶음을 찾는 문제이다. 묶음을 찾는 문제들은 DFS로 구현이 가능하다. 처음 구현 코드 DFS익숙하지 않아서 이전에 풀었던 DFS틀에 맞춰서 풀지 못하였다. n = int(input()) graph = [list(map(int, input())) for _ in range(n)] def dfs(x, y, house_count): if x = n or y = n: return False if graph[x][y] == 1: graph[x][y] = house_count dfs(x - 1, y, house_count) dfs(..