본문 바로가기

728x90

알고리즘 문제 풀이/DFS,BFS24

[백준]4963번: 섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net dfs로 풀었더니 RecursionError가 나서.. 이유를 찾아보니까 BOJ 채점 서비스에서는 파이썬 최대 재귀 깊이가 1000으로 설정되어 있다고 한다. 그러니깐 테케중에서 재귀를 1000번 이상 수행하는 게 있었나보다 \해결법은 여러 가지가 있는데 그중에서 젤 쉬운거 선택함 ^v^ import sys sys.setrecursionlimit(10**6) 최대재귀깊이를 임의로 겁나 큰 수.. 2023. 2. 23.

[이코테]미로 탈출 / [백준]2178번: 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net from collections import deque #미로 정보 입력받기 n, m = map(int,input().split()) graph=[] for i in range(n): graph.append(list(map(int,input()))) #상하좌우 좌표 dx=[-1,1,0,0] dy=[0,0,-1,1] #(0,0) 시작점으로 bfs 수행 q=deque() q.append((0,0)) while q: x,y = q.po.. 2023. 2. 23.

[이코테] 음료수 얼려 먹기 출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈) https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 문제 N * M 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려 있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다. 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요. 문제 조건 입력 조건: 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어집니다. (1 2023. 2. 23.

dfs, bfs 파이썬 구현 dfs def dfs(graph, v, visited): visited[v]=True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(graph,i,visited) graph=[ [], #인덱스 0은 비워둠 [2,3,8], #첫번째 노드와 인접한 노드 목록 [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False]*9 dfs(graph,1,visited) bfs from collections import deque def bfs(graph, v, visited): q=deque([v]) #큐 생성 visited[v]=True #방문처리 while q: #큐가 비어있지 않은동안 w .. 2023. 2. 23.

[백준]2644번: 촌수계산 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net #include using namespace std; int n,m; int graph[101][101]; bool visited[101]; int cnt=0; int ans=-1; void dfs(int x,int y){ if(x==y) ans=cnt; visited[x]=1; cnt++; for(int i=0;i>n; int x,y; cin>>x>>y; cin>>m; for.. 2023. 2. 18.

[백준]2667번: 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net bfs로 풀었음 코드가 약간 지저분한 느낌이다,, #include #include #include #include using namespace std; int n; int map[25][25]; //지도 bool visited[25][25]; //방문 체크 queue q; int cnt=0; //단지별 집의 개수 count vector v; //단지별 집의 개수 저장 int bfs(int x, in.. 2023. 2. 15.

이전 1 2 3 4 다음

728x90

티스토리툴바