문제 설명 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 문제 풀이 bfs를 두 번을 해야 하는 문제는 처음이라 풀이 방향을 잡는데 어려웠다 일단 불이 확산되는 시간을 구하고, 그 다음에 지훈이가 탈출할 수 있는지 확인해야 하기 때문에 BFS를 두 번 수행해야 한다 지훈이가 미로 공간을 벗어나면 미로를 탈출하는 것이기 때문에 바로 return을 해줬다 BFS는 거리 순서대로 탐색해서 무조건 최소 시간이 맨 처음에 들어오기 때문..
분류 전체보기
문제 설명 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 전형적인 BFS 문제 시작점이 여러 개인 BFS 문제를 처음 풀어봐서 풀다가 당황 ,,,, BFS 자체가 너비 우선으로 탐색하기 때문에 1일차, 2일차 이렇게 순서대로 큐에 들어간다 처음 시작점을 찾은 후 큐에 넣은 다음 BFS를 수행하면 된다 ! 다 풀고 나서 코드 리뷰를 해본 결과 bfs 함수 안에서 큐를 다 돌고 나서 안 익은 토마토가 있을 때(값이 0일..
문제 설명 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 풀이 visited로 방문 여부를 기록하였고, 이중 포문으로 값이 1이면서 아직 방문하지 않은 지점일 때 bfs를 시작하여 bfs의 시작점을 구했다. 가장 넓은 그림의 넓이를 출력하기 위해 max를 사용하여 비교했다! from collections import deque n, m = map(int, input().split()) visited = [[False] * m for _ in ..
문제 설명 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 가장 기본적인 BFS 문제 경로의 최단 거리를 구하는 문제이기 때문에 BFS로 풀었다 만약 경로가 몇 가지인지를 묻는다면 DFS로..! 미로 범위에서 벗어난 경우이거나, 이동할 수 없는 칸을 무시하고 해당 칸을 처음 방문했을 때 이전 지점까지의 최단거리 + 1 해주었다 from collections import deque def bfs(x, y): queue = deque() queue.append((x, ..
대표 문제 유형 경로 탐색 (최단 거리, 시간) 최단 거리 : BFS 경로의 가짓수(경우의 수) : DFS 네트워크 (연결) 조합 (모든 조합 만들기) 구현 방법 DFS : Stack, 재귀함수 BFS : Queue, LinkedList 무방향 그래프 # 각 노드가 연결된 정보를 표현 (2차원 리스트) # 보통 문제에서 1부터 시작하기 때문에 인덱스 0은 비워둠 graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 표현 (1차원 리스트) visited = [False] * 9 DFS (Depth First Search) DFS를 설명할 때는 보통 ‘번호가 낮은 인접 노드부터 방문..
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음에는 유효기간을 년, 월, 일 전부 구하려고 애를 먹었는데... 풀이하다 막혀서 문제를 다시 읽어보니까 굳이 정확한 일자를 구할 필요가 없다고 생각했다. 약관의 타입을 찾는 시간을 줄이기 위해, 편하게 찾기 위해 딕셔너리를 사용하였다. 개인정보의 년, 월, 일을 구한 다음에 약관의 유효 기간을 더해주었고, 더한 값이 12의 배수면 12월로 만들어줘야 하기 때문에 if문으..
