4179번: 불!입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자www.acmicpc.net 반나절 삽질한 BFS문제. 문제가 어렵게 느껴지진 않았는데 시간초과, 메모리초과 등등 오답파티가 됐다.아이디어- 문제에서 탈출 조건이 가장자리에 접한 공간에서 탈출할 수 있다고 한다. 이 말은 지훈이가 가장자리에 도착만 하면 자동으로 탈출 가능하다. - 순서는 지훈이가 한번 이동하고 나서 불이 확산되고 1초가 지난다. - 만약 지훈이가 이동한 후 위치에 불이 번진다면 그곳은 못 가는 위치이다. - 이 문제를 해결하려면 지훈과 불 각각의 큐를 만들어서..
1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 활용한 최소 시간을 구하는 문제. 아이디어 현재 위치(x)에서 갈 수 있는 거리는 x - 1, x + 1, x * 2이다. 각 경우마다 if문을 통해 조건을 확인해준다. 이전에 방문하지 않은 위치라면 그 위치까지 걸리는 시간들을 BFS방식으로 순회하며 시간을 저장해준다. 전체 코드 from collections import deque N, K = map(int, input().split()) deq = deque() deq.a..
14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 지도에서 모든 지점의 최단거리를 구하는 문제. 아이디어 BFS를 사용했다. 지도에서 최단거리 == BFS 거의 공식처럼 머리에서 나온다... 문제를 해결하기 위해 목표 지점(2로 표시)과 갈 수 없는 땅(0으로 표시)의 좌표는 따로 저장해 둔다. 전체 코드 from collections import deque dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] start_x, start_y = 0, 0 ..
21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 평범한 그래프 탐색 문제. 아이디어 bfs 또는 dfs를 활용하여 문제를 해결하면 된다. 1. 그래프 시작지역 'I'는 캠퍼스 정보를 받아올 때 미리 찾아둘 수 있다. 2. 빈공간 뿐아니라 사람이 있는 지역 'P'도 이동 가능하다. 3. 정답을 출력할 때, 답이 0명이면 0이 아닌 "TT"를 출력해 주자. 전체 코드 from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] campus =..
https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 맨해튼 거리인 줄 모르고 삽질했다. 문제를 잘 읽어보자. 아이디어 1. 그래프 탐색 심플하게 맥주 20병 = 1000m라고 생각하고 1000m를 기준으로 갈 수 있는지 없는지 확인하면 된다. bfs를 사용하여 해결했다. 전체 코드 from collections import deque def cal_distance(x, y, nx, ny): return abs(nx - x) + abs(ny -..
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 시리즈 마지막 숨바꼭질 1 먼저 풀어보는 게 좋다. 아이디어 1. bfs 큐에 x +1, x - 1, x * 2를 조건에 맞으면 추가해준다. 큐에 위치와 시간 그리고 지나온 길도 같이 넣어준다. 도착하면 도착 시간과 경로를 리턴 후 출력. 전체 코드 from collections import deque N, K = map(int,input().split(..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 1. bfs 이미 숨바꼭질 1과 3을 풀어서 대충 알고 있다. x - 1, x + 1, x * 2 큐에 넣어주면서 탐색하면 됨. 경우의 수를 어떻게 구할지 생각만 하면 된다. 2. 경우의 수 쭉 탐색을 하다가 맨 처음 동생한테 도착한 시간을 저장하고 이후 동생한테 도착했을 때 저장해둔 시간과 같다면 경우의 수를 +1 해준다. 전체 코드 from col..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 아이디어 1. 반복문 문제 느낌이 진실을 아는 사람이 좀비같이 감염시키는 것이라 생각 그래서 진실을 아는 사람과 같이 있는 사람들을 진실을 아는 사람으로 바꿨다. 근데 이러면 진실을 아는 사람들이 바뀌어서 전체 파티를 또 탐색해야 하고 이를 계속 반복해야 해서 실패했다. 2. 그래프 그러다가 동시에 한 번에 해야 된다는 것을 깨닫고 그래프를 사용하기로 결정 각 파티마다 있는 사람들을 두 명씩 양방향으로 이어..
