https://www.acmicpc.net/problem/16234 bfs를 여러번 돌려서 구역을 찾는 문제다이렇게 반복을 많이 해도 되나..? 싶은 문제들은 보통 입력의 크기가 20,50,100 이정도 수준이므로 걱정하지 않아도 된다.다만 좀 까다로운 점은 구역을 나중에 계산해줄 때이다 그냥 배열 하나 더 만들어서 연합(구역)별 값을 따로 저장해주고, country 리스트를 한번 더 돌면서 값을 일일이 넣어주었다. 더 좋은 방법 있으면 댓글로 공유 부탁드려요!from collections import dequeN, L, R = map(int, input().split())country = []for _ in range(N): arr = list(map(int,input().split())) ..
https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/ai-robot/description 코딩테스트 기출 문제 설명: AI 로봇청소기 | 코드트리코딩테스트 기출 문제 AI 로봇청소기의 상세 설명입니다. 문제 요구사항을 정확히 파악하고 효율적인 알고리즘을 설계해보세요.www.codetree.ai사실 그렇게 깔끔한 코드는 아니지만,, 기록해둘겸 작성해봅니다.. 패턴이 주어지고, 이를 방향에 따라 다르게 적용하는 코드는 백준의 마법사 상어와 토네이도 문제에서 영감을 받았습니다.https://www.acmicpc.net/problem/20057 이 문제는 'bfs', 'tie break', 'origin' 이 3가지가 키워드였다고 생각합니다. 비교..
https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알파벳 한글자만 변환해서 target 단어에 도달하는 bfs문제이다. 완전탐색이 아니라 bfs 카테고리에 분류된 이유는 다음과 같다. 1. hit -> hot -> lot, dot ,, 2. lot -> log -> cog 2. dot -> dog -> cog 처럼 탐색이 진행되기 때문이다. 단어를 비교하여 오직 한 알파벳만 차이나는 경우 큐에 담아주고 bfs 탐색을 진행하면 된다. 다만 hot ..
https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 Level 3 정도의 문제지만, 백준으로 치면 다른 트릭이나 복잡한 구현이 없는 기본적인 bfs/dfs 문제라서 골드 4-5정도 될 것 같다. 아무튼, 이 문제의 풀이에 대해 알아보자 문제에서 찾고자 하는 것은 '연결된 영역의 개수' 라고 할 수 있다. n은 반드시 1 이상, 즉 주어진 그래프에는 노드 1이 반드시 존재함을 알 수 있다. 1을 기점으로, 재귀 형식의 dfs를 이용해 아..
https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 그래프 문제이다 딱히 추가적으로 구현해야 할 건 없고, 양방향 그래프를 잘 입력받은 뒤 bfs로 탐색을 해주면 된다 간선에 가중치가 붙으면 다익스트라를 이용해주면 된다 from collections import deque def solution(n, edge): answer = 0 graph = [[] for _ in range(n+1)] visited = [False] *(n+1) dist = ..
https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 까다로운 조건이 없는 BFS 문제이다 한가지 팁은, 아래의 cnt 변수를 어떻게 잘 조작하면 굳이 방문 배열을 사용하지 않고도 풀 수 있다는 점을 잘 생각해보시길.. from collections import deque def solution(maps): answer = -1 dq = deque() dq.append([[0,0],1]) end_x, end_y = len(maps), len(maps[..
