프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr BFS를 활용하면 되는 문제.기본 BFS 문제 로직과 거의 유사하지만 다른 점이 한 가지 있다.로봇이 한 칸씩 이동하는 게 아니라, 장애물에 부딪히거나 맵의 끝에 도달할 때까지 한 방향으로 계속 이동하고, 멈췄을 때까지 시간을 1로 친다는 것이다.그 부분을 반복문을 통해 구현해줬다. 풀이 코드from collections import dequedef solution(board): n = len(board) # 행 길이 m = len(board[0]) # 열 길이 visited = [..
BFS
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.krBFS로 풀면 되는 문제. BFS 탐색 함수를 따로 구현해서시작지점 ~ 레버까지의 최단거리, 레버 ~ 도착지점까지의 최단거리를 각각 구한 후 더해주면 된다.만약 2가지 최단거리 중 하나라도 None이 나오는 경우에는 도착이 불가능한 경우이므로 -1을 리턴해준다. 풀이 코드from collections import deque# BFS 돌리기def bfs(maps, start_x, start_y, end_x, end_y, end_val): n = len(maps) m = len(maps[0]) ..
프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 전형적인 탐색 문제.DFS/BFS를 활용해서 풀 수 있다. DFS 풀이 코드import syssys.setrecursionlimit(int(1e9)) dx = [-1, 1, 0, 0]dy = [0, 0, 1, -1]foods_sum = 0def dfs(x, y, visited, maps): global foods_sum n = len(maps) m = len(maps[0]) visited[x][y] = True # 방문 처리 foods_sum += int(maps[x][y]..
https://www.acmicpc.net/problem/1926 DFS # 1926번: 그림(DFS)import syssys.setrecursionlimit(10**6)cnt = 0 # 그림의 개수max_area = 0 # 가장 넓은 그림의 넓이n, m = map(int, input().split())visited = [[False]* m for _ in range(n)]arr = []for _ in range(n): arr.append(list(map(int, input().split())))dx = [0, 0, 1, -1]dy = [1, -1, 0 , 0]def dfs(x, y): visited[x][y] = True global area for i in range(4):..
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 ..
다익스트라 알고리즘을 이용해 1번 노드 ~ 다른 모든 노드까지의 최단 거리를 구하면 나오는 distance 리스트를 통해 풀 수 있는 문제. 여기서는 각 노드 사이의 거리가 1이기 때문에 BFS를 이용해서도 풀 수 있지만, 다익스트라 알고리즘을 사용하면서 각 노드 사이의 거리를 1로 넣어주면 다익스트라 알고리즘으로도 풀 수 있다. 내 풀이 코드 # 숨바꼭질 import heapq, sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] # (도착노드, 거리)를 저장하기 위한 리스트 distance = [INF] * (n+1) # 최단거리를 저장하기 위한 리스트 ..
