모각코 3회차 - 각자 문제풀이

컴퓨터 공부/👨‍💻 모각코

모각코 3회차 - 각자 문제풀이

letzgorats 2022. 11. 11. 02:29

모각코 두번째 회의 후 각자 코딩 테스트를 위한 문제풀이를 진행했습니다!

저는 구름 LEVEL 에서 2시간의 시간제한을 두고 챌린지 문제들을 풀어봤습니다.

그 중에서 복기할만한 문제들을 추려보겠습니다.

✏️ 준비운동 PART3. 각자 문제풀이

1. 개미와 진딧물

한 변의 길이가 N 인 정사각형 모양의 평면에 진딧물 집과 개미 집이 있다. 개미 집은 고유의 영역 범위 안의 모든 진딧물에게서 수액을 수집한다. 이 수액이 없으면, 개미 집은 부족한 식량으로 제거된다.

길이가 4 인 정사각형 평면을 1X1 크기의 작은 정사각형으로 나누면 아래와 같은 그림으로 표현할 수 있다.

위와 같은 상태로 arr[i][j] 값들이 주어진다. arr[i][j] 의 값은 0,1,2 중 하나이며, 1은 개미 집이고, 2는 진딧물이다. 아래 조건에 따라 개미 집은 제거된다.

arr[i][j] 이 개미 집이라면, M칸 안에 진딧물이 없을 때 제거된다.
이 때 거리를 측정하는 방법은 상하좌우 인접한 칸으로 한 번 이동할 때 마다 1칸 움직인 것으로 한다.

위의 규칙에 따라 개미 집이 제거되었을 때, 남아있는 개미 집의 개수를 출력하시오.

한 변의 길이가 N인 정사각형 모양의 평면에서 개미집(1)을 찾고 거리 M을 고려한 주변에, 진딧물(2)가 있는지 없는지에 따라 개미집을 제거할지 안할지 결정하는 로직이었습니다.

처음에 접근한 코드는 테스트케이스는 통과했지만, 제출시에는 몇 문제가 틀렸다고 나왔습니다.

처음 푼 코드는 아래와 같습니다.

import sys
input = sys.stdin.readline

N , M = map(int,input().split())	# 정사각형의 크기 N, 거리 M

graph = [list(map(int,input().split())) for _ in range(N)]	# 평면 그래프 입력

dr = [-1,1,0,0]	# 행 - 상 하 좌 우 
dc = [0,0,-1,1] # 열 - 상 하 좌 우
total = 0	# 총 개미집 개수
cnt = 0 # 개미집을 제거해야 하는 경우를 나타내는 변수

# 1 == 개미집, 2 == 진딧물
for i in range(N):
	for j in range(N):
		if graph[i][j] == 1:	# 개미집인 위치 주변만 탐색
			total += 1
			alive = False		# 개미집을 제거할지 안할지를 나타내는 변수 
			for d in range(4):	# 상 하 좌 우 4방향
				for m in range(1,M+1):	# 1부터 M까지의 거리만큼을 고려
					nr = i + dr[d] * m
					nc = j + dc[d] * m
					if 0<= nr < N and 0<= nc < N:	# 범위 안이라면,
						if graph[nr][nc] == 2:		# 진딧물(2)가 있다면,
                      		# 제거 안해도 된다. alive를 True값으로 갱신
							alive = True			
							break			# 탈출
				if alive:	# alive가 True면
					break	# 탈출
				if alive == False:	# alive가 False면
					cnt += 1	# 개미집 제거해야 한다.
				
print(total - cnt)

생각을 계속 해봐도 왜 틀렸는지 감이 안 잡혔습니다. 놓친 부분은 바로 이 그림을 보니 알 수 있었습니다.

개미집(1)을 기준으로 거리를 고려한 (상,하,좌,우)만 생각했었는데, 대각선도 고려해야 하는 것을 놓쳤습니다.

윗 부분과 아랫부분으로 나눠서 고려한 코드는 아래와 같습니다.

* 개미 집을 기준으로 진딧물 찾기

import math
import sys
input = sys.stdin.readline

N , M = map(int,input().split())	# 정사각형의 크기 N, 거리 M

graph = [list(map(int,input().split())) for _ in range(N)]	# 평면 그래프 입력

dr = [-1,1,0,0]	# 행 - 상 하 좌 우 
dc = [0,0,-1,1] # 열 - 상 하 좌 우

ant_alive = 0

def search(r,c,m):
	# 윗 부분 탐색
    for i in range(m, -1, -1):
        for j in range(-i, i + 1):
            if 0 <= r-  m + i < N and 0 <= c + j < N:
                if graph[r -m + i][c + j] == 2:
                    return True
    # 아랫 부분 탐색
    for i in range(1, m + 1):
        for j in range(-m + i ,m - i + 1):
            if 0 <= r + i < N and 0 <= c + j < N:
                if graph[r + i][c + j] == 2:
                    return True
    return False


# 1 == 개미집, 2 == 진딧물
for i in range(N):
	for j in range(N):
		if graph[i][j] == 1:	# 개미집인 위치 주변만 탐색
			if search(i,j,M) : # 진딧물(2) 이 있으면
				ant_alive += 1			
				
print(ant_alive)

* 좌표끼리만 비교해서 풀기

윗부분 탐색 아랫부분 탐색이 조금 생각해야 하고 복잡하다면, 좌표끼리만을 이용해서 풀 수도 있습니다. 이 때는, 맨하튼거리 개념을 이용하면 됩니다.

# 맨하튼 거리 pos => (x, y), abs => 절대값 함수
def manhattan(pos1, pos2):
return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

좌표끼리만을 고려하면, 완전탐색으로 풀이가 가능합니다.

조금 더 직관적으로 풀 수 있는 코드는 아래와 같습니다.

import math
import sys
input = sys.stdin.readline


def manhattan(pos1, pos2):
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])
	
N , M = map(int,input().split())	# 정사각형의 크기 N, 거리 M

graph = [list(map(int,input().split())) for _ in range(N)]	# 평면 그래프 입력

position_1_list = list()
position_2_list = list()


# 1 == 개미집, 2 == 진딧물
for i in range(N):
	for j in range(N):
		if graph[i][j] == 1:	# 개미집 위치 저장
			position_1_list.append([i,j])
		if graph[i][j] == 2:	# 진딧물 위치 저장
			position_2_list.append([i,j])

cnt = 0

for pos1 in position_1_list:
    idx = 0
    while True:
        if idx == len(position_2_list):
            break
        pos2 = position_2_list[idx]
        if manhattan(pos1, pos2) <= M:
            cnt += 1
            break
        else:
            idx += 1
print(cnt)

2. 순환하는 수로

구름이는 도시의 물을 관리하는 관리자이다. 현재 도시에는 물을 잠시 보관하는 물탱크와 물탱크끼리 연결하는 수로가 아래의 조건으로 설치되어 있다.

N개의 물탱크와 N개의 수로가 있다.
물탱크는 1번부터 N번까지 있다.
수로가 연결된 물탱크는 양 쪽으로 물이 흐른다.
서로 다른 두 물탱크를 잇는 수로는 최대 하나이다.
물탱크에서 연결된 물탱크는 항상 다른 물탱크이다.
모든 물탱크는 연결되어 있다. 즉, 어떤 물탱크에서 임의의 다른 물탱크로 항상 물이 흐를 수 있다.

도시의 물은 흐르지 않으면 녹조류가 생기기 때문에, 항상 물이 순환하도록 유지하는 것이 중요하다.

하지만, 구름이는 순환하는 물이 항상 모든 물탱크를 지나지 않는다는 점을 확인했다. 구름이는 현재 상태의 수로를 확인하고, 순환하는 수로를 찾기로 한다. 이때 순환하는 수로란, 물탱크의 물이 아래의 조건을 만족하면서 끊임없이 순환해야 한다.

모든 물탱크에는 물이 없는 상태에서 시작한다.
최초의 하나의 물탱크를 선택하여, 물을 채우고 물탱크에 연결된 다른 물탱크에 물을 공급한다.
다른 물탱크에 물을 공급하는 물탱크는 물이 모두 비워질 때까지, 다른 물탱크에 공급한다.
순환하는 수로의 정의를 다음과 같이 정의하자. 어떤 물탱크에 있던 물이 특정한 수로들을 거쳐 다시 원래의 물탱크로 돌아올 때, 그 수로들의 집합을 순환하는 수로라 한다.
순환하는 수로의 집합의 크기는 최소 3개 이상이어야 한다.

아래의 예시를 들어보자.

위의 예시에서 최초로 1번 물탱크에 물을 채우고, 다른 물탱크에 공급을 시작한다.

1번 물탱크에 연결되어 있는 다른 모든 물탱크에 물이 공급된다. 2번 물탱크에 물이 공급이 되면, 2번 물탱크는 물을 공급해준 1번 물탱크를 제외하고 3, 4번 물탱크에 물을 공급한다.

3번 물탱크의 물 흐름은 {3 > 4 > 2}, {5 > 3 > 4} 를 거친다. 5번 물탱크로 간 물은 다시 물을 공급해준 4번 물탱크로 올 수 없으며, 2번 물탱크는 물을 공급해준 4번과 1번 물탱크로 물을 공급할 수 없다.
4번 물 탱크의 물 흐름은 {4 > 2}, {5 > 3 > 4 > 3} 을 거친다.

물은 조건에 따라 흐르기 때문에, {2 > 3 > 4} 물 탱크만 흐르게 된다. 이를 보고 순환하는 수로라고 한다.

구름이가 도시의 물 탱크의 개수와 수로의 상태가 주어졌을 때, 가장 큰 순환하는 수로를 찾고, 수로의 집합의 크기와 번호를 오름차순으로 출력하시오. (단, 항상 순환하는 수로가 존재한다)

문제의 해설은 BFS, DFS를 돌려서 풀었습니다. 하지만, 더 간단하게 푸는 방법이 존재합니다.

먼저, 문제 조건을 잘 보면, "서로 다른 두 물탱크를 잇는 수로는 최대 하나이다" 라고 했습니다.

노드들 중에 간선이 하나라면 사이클을 이루고 있지 않다는 얘기입니다.

최소 2개 이상의 간선이 노드에 연결되어야 그 노드는 사이클에 포함될 수 있기 때문입니다.

그렇기 때문에, 사이클을 이루고 있지 않은 노드는(간선이 1개만 연결되어 있는 노드는) 그 간선과 노드를 그래프에서 제거해가면, 남아있는 사이클이 곧 답입니다.

그 사이클을 형성하는 노드의 번호를 오름차순으로 출력하면 끝입니다.

import sys
input = sys.stdin.readline

N = int(input())	# 물탱크의 수(수로의 수)

graph = [[] for _ in range(N+1)]
edges = [0 for _ in range(N+1)]

cycle = []	# 사이클을 형성하는 물탱크 집합

for _ in range(N):
	a, b = map(int, input().rstrip().split())
	# 양방향 연결
	graph[a].append(b)
	graph[b].append(a)
	# 간선 1 증가
	edges[a] += 1
	edges[b] += 1

flag = False
while True:
	if flag:	# flag가 True면 더 이상 간선이 1개인 노드가 없는 것-> 사이클만 존재
		break
	else:
		flag = True
		for i in range(1,N+1):
			if edges[i] == 1:	# 간선이 1개만 연결되어 있다면,
				j = graph[i][0]	# i와 연결된 노드 꺼내고
				graph[i] = 0	# graph[i]는 이제 아무것도 연결x
				graph[j].remove(i)	# graph[j]에서도 노드 i 제거
				
				edges[i] -= 1	# 노드 i와 연결된 간선 하나 제거 -> 0이 된다. 
				edges[j] -= 1	# 노드 j와 연결된 간선도 하나 제거 
				flag = False	# flag 다시 False로 갱신
				break

for i in range(1,N+1):
	if edges[i] > 0 :
		cycle.append(i)
		
print(len(cycle))
print(*cycle)

* 구름에서 제시한 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
from collections import defaultdict

n = int(input())
graph = defaultdict(list)
for i in range(n):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)
visited = [0 for _ in range(n+1)]
circle = list()
finded = -1
def FindCycle(u, tar):
    global finded
    if visited[u] == 1:
        finded = u
        if u not in circle:
            circle.append(u)
        return
    visited[u] = 1
    for i in graph[u]:
        if i == tar:
            continue
        FindCycle(i, u)

        if finded == -2:
            return
        if finded == u:
            finded = -2
            return

        if finded >= 0:
            if u not in circle:
                circle.append(u)
            return
FindCycle(1, 1)
circle.sort()
print(len(circle))
for i in circle:
    print(i, end = ' ')

저작자표시

'컴퓨터 공부 > 👨‍💻 모각코' 카테고리의 다른 글

모각코 6회차 - 웹 스크래핑을 통한 정보 추출 (0)	2022.11.30
모각코 5회차 - DBMS 성능 개선 알고리즘 소개 (0)	2022.11.30
모각코 4회차 - SQLD 자격증 공부 (0)	2022.11.14
모각코 2회차 - 약점체크 (0)	2022.11.10
모각코 1회차 - 준비운동 (2)	2022.10.05

현재글모각코 3회차 - 각자 문제풀이

알루 코딩