본문 바로가기

728x90

그래프2

[백준] 2667. 단지번호붙이기/Python - Silver 1 ❓문제https://www.acmicpc.net/problem/2667성능 요약메모리: 108548 KB, 시간: 92 ms분류너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.✍🏻풀이각 단지에 속하는 집의 수.. 2025. 2. 5.

[프로그래머스] 순위/Python - Lv.3 ❓문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 📌유형그래프, Floyd-Warshall✍🏻풀이1) 그래프 자료구조 사용- 이긴 그래프와 진 그래프를 인접 리스트 형태로 만듦.- 1은 2번을 이김. 1번의 이긴 그래프에 2번에게 진 5번 노드를 업데이트.- 1은 누구에게도 지지 않음.- 2번은 5번을 이기고, 1, 3, 4번에게 짐. 1, 3, 4번 이긴 그래프에 5번을 업데이트. 5번 진 그래프에는 1, 3, 4번을 업데이트.- 각 노드의 이긴 그래프와 진 그래프의 길이의 합이 n - 1과 같다면 answer를 1 증가.2) Floyd-Warsh.. 2024. 9. 28.

이전 1 다음

728x90

티스토리툴바