방앗간 개발자

문제 출처:https://www.acmicpc.net/problem/16234

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

문제 자체는 DFS나 BFS를 이용하여 조건에 맞추어 인구 이동이 가능한 영역을 구하고 이 영역 안에서 인구 이동을 시킵니다.

이 인구 이동을 더 이상 불가능 할때까지 계속 반복하며 인구이동 발생 수를 체크만 해주면 되는 비교적 간단한 문제인데 

저는 문제에서 말하는 '인구 이동'을 잘 못 이해하여 문제를 푸는데 한참 걸렸습니다.

제가 헷갈린 인구 이동은 아래와 같습니다.

L = 10, R = 50

이런 형태로 입력이 주어졌다고 합시다.

주어진 배열에 대하여 인구 이동이 가능한 영역을 위와같이 구해줍니다.

조건에 맞게 배열을 변형시켜준 뒤 인구 이동 횟수를 1 증가시킵니다. 

변형된 배열에 맞추어 한번 더 인구 이동이 가능한 영역을 구합니다.

여기서 한 구역을 조건에 맞추어 바꿔주었는데 이 때 인구 이동 횟수를 1 증가시키면 안됩니다. 

이렇게 모든 영역을 전부 다 바꿔준 뒤에야 인구 이동 횟수를 1 증가시켜주어야 합니다.

저는 처음에 구역 한개가 바뀔때마다 인구 이동 횟수를 증가시키는 줄 알고 한참을 고생했습니다.

이 부분만 주의해서 풀면 그렇게 어렵지 않게 풀이가 가능할거라 생각됩니다.

그리고 더 이상 인구 이동이 가능하지 않아서 프로그램을 종료하는 조건은 저의 경우 아래와 같은

형식으로 풀었습니다.

위의 배열에 대하여 영역을 구했을때 똑같은 크기의 배열을 하나 더 만들어 아래처럼 숫자로 각 구역을 

표시 해 주었습니다. 따라서 어떤 배열이 주어졌을때 아래처럼 영역을 숫자로 나타낸 배열이 

이와 같은 형식을 나타낸다면 모든 구역이 전부 독립적인 영역을 가진다는 의미이므로 이 때 프로그램을 

종료시켜 주었습니다.

전체 코드입니다.

문제 출처:https://www.acmicpc.net/problem/1325

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

위 그림은 출처에 있는 예제 입력을 그림으로 나타낸것인데 여기서 주의 하셔야 하는점은 그래프에 방향이 있는 방향 그래프 

란 것이고 입력에 대한 신뢰 관계를 이런식으로 표현해주어야 DFS, BFS연산을 수월하게 수행 할 수 있습니다.

위 그림에 대한 정답은 1,2번 노드가 각각 총 4개의 노드를 해킹 할 수 있기 때문에 1,2번 노드가 정답이 됩니다.

이제 문제를 풀어보자면 일단 그래프를 표현하는 것 부터 시작인데 그래프를 인접 행렬 그래프로 표현 한다면 문제의 n 값이 

최대 10,000이므로 2차원 배열 graph[10,000][10,000] 을 만들면 메모리 초과 오류가 나게됩니다. 따라서 그래프는 인접 리

리스트 그래프를 사용해야 됩니다.

인접 리스트로 그래프를 만들었다면 이제 모든 노드에 대해서 DFS, BFS연산을 수행하고 가장 많이 해킹 할 수 있는 노드를 찾

아서 오름차순으로 출력해주면 됩니다. 

저의 경우는 처음에 재귀를 이용한 DFS를 사용한다면 시간초과가 뜰거라 생각하고 큐를 이용한 BFS방법으로 문제를 풀었는

데 무엇이 잘못된건지 계속 시간초과를 받아서 결국 재귀를 이용한 DFS로 문제를 풀었습니다.

문제 출처:https://www.acmicpc.net/problem/10026

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

DFS, BFS 알고리즘을 이용하는 기초적인 문제입니다.

배열에서 R, G, B 각각의 영역 갯수를 구하는 문제인데 제약조건이 하나 붙습니다.

R, G, B에 대한 영역 (R, G), B에 대한 영역 갯수 2가지를 구하여야 합니다.

저는 처음부터 2차원 배열을 2개 만들어서 입력받을때 한 배열은 R, G, B 그대로 만들고

다른 배열은 (R, G)를 같은 영역으로 입력받아 그 2개의 배열에 각각 DFS 알고리즘을

수행하여 영역의 갯수를 구하는 방식으로 문제를 풀었습니다.

입력받을때 2가지 배열로 나누어 입력받는 코드입니다.

영역의 크기를 구해주는 DFS알고리즘 코드 입니다.