본문 바로가기

Problem Solving/boj68

[BOJ] 17836. 공주님을 구해라!(Python) / BFS 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 재미있는 BFS 너비우선탐색 문제였다. # 45분 소요 처음에 풀 때 한 번에 답이 나왔지만, 세세한 케이스들을 미처 다 생각하지 못해서 여러 번 제출하며 조건문을 계속 추가했고, 결국 맞았다! 기본적인 BFS 틀에서 내가 고려한 조건은 다음과 같다. 격자에서 이동 중 그람(2)를 만났을 때, 현 위치에서 목적지까지는 거리를 절댓값의 합(minTime)으로 구해 미리 저장해둔다. 목적지까지 정상 도달한 경우도 도중에 그람을 구했든 아니든 반드시! .. 2021. 3. 25.
[BOJ] 2846. 오르막길(Python) www.acmicpc.net/problem/2846 2846번: 오르막길 상근이는 자전거를 타고 등교한다. 자전거 길은 오르막길, 내리막길, 평지로 이루어져 있다. 상근이는 개강 첫 날 자전거를 타고 가면서 일정 거리마다 높이를 측정했다. 상근이는 가장 큰 오르 www.acmicpc.net 브론즈 문제로, 최장 길이를 구하기보다 가장 차이가 많이 나는 오르막길을 구하는 것이다. 이중 for문으로 오르막을 만날 때마다 가장 낮은 부분과 비교해 차이(maxDis)를 갱신해준다. 설명보다 아래 코드를 보는 것이 더 빠른 이해를 도울 것 같다. 파이썬 코드는 다음과 같다. from sys import stdin input = stdin.readline N = int(input()) A = list(map(int.. 2021. 3. 23.
[BOJ] 13023. ABCDE(Python) / DFS www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 깔끔한 DFS 문제였다. input 받으면서 정점별로 갈 수 있는 정점의 정보를 딕셔너리에 담는다. 전역변수 flag를 두어 depth가 4이상 되면 1로 바꿔주며 return하여 더이상 진행하지 않는다. 모든 정점에서 start할 수 있다. visited로 아직 방문하지 않는 곳에 방문체크하며 다음 재귀로 넘어간다. 재귀 풀려 나올 땐 방문체크한 것을 0으로 돌려 놓는다. flag가 1이면 1, 0이면 0을 출력한다. 파이썬 코드는 다음과 같다. import sys input = sys.stdin.readline .. 2021. 3. 23.
[BOJ] 6087. 레이저 통신(Python) / BFS www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 연속으로 BFS 최단거리 문제를 풀었다. 문제를 처음 접했을 때 이전의 로봇 문제처럼 맵을 방향별로 만들어줘야겠다는 생각을 했는데, 조금 더 생각해보니 그렇게까지 할 필요는 없을 것 같고, 머릿 속으로 BFS 이차원 맵을 어떻게 채울지 생각했다. 초기 check 맵을 최댓값 float('inf')으로 채워 놓는다. 시작 위치에서 4방향으로 쭉쭉 직진으로 벽이나 격자 밖으로 나갈 때까지 그려주고, 그 다.. 2021. 3. 22.
[BOJ] 1726. 로봇(Python) / BFS www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net BFS 최단거리 문제다. 처음에 문제 봤을 때 어떻게 풀어야할지 좀 막막했는데 여러 솔루션들을 보고 아이디어를 얻었고, 특히, 뚱이가 코드를 보내줘서 완벽히 이해할 수 있었다. 내 스타일대로 다시 풀어봤다. 이 문제에서 포인트는 visited를 맵의 크기대로 그리되, 각 위치별로 4방향(동서남북) 정보를 담을 수 있도록 * 4 해주는 것! 큐에 위치와 방향, 그리고 cnt값을 담았다. 해당 정보를 visited에 표시하며.. 2021. 3. 22.
[BOJ] 1342. 행운의 문자열(Python) / DFS www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 내가 짠 코드는 15분만에 간단한 DFS로 순열(Permutation)을 구현했지만, 중복 고려하지 않고 문자열 그대로 완전탐색해버리니, 3300ms로 겨우 통과했다.. 부끄러워서 차마 내 코드는 올릴 수가 없다. 이번에 소개할 코드는 내가 짠 건 아니고, "뚱이"라는 나의 짝꿍이 짰다. 토실토실 아주 귀여운 친구다. 문자열의 각 알파벳별 카운트로 계산한다. 아스키 코드 변환(ord()함수 사용)으로 a~z까지 0~.. 2021. 3. 18.

티스토리툴바