[백준] IP 주소

[출처] https://www.acmicpc.net/

알고리즘 분류 : 구현, 비트마스킹

문제

네트워크에 연결되어 있는 컴퓨터들은 각각 하나의 IP 주소를 갖게 된다. 그리고 이러한 IP 주소를 갖는 컴퓨터들이 여러 개 모여서 하나의 IP 네트워크를 구성하게 된다. IP 네트워크는 ‘네트워크 주소’와 ‘네트워크 마스크’라는 두 개의 정보로 표현된다.

IP 주소는 네 개의 바이트로 구성되어 있으며, 각각을 10진수로 나타내고(앞에 0을 붙이지 않은 형태로) 사이에 점을 찍어 주소를 표현한다. 바이트이기 때문에 각각의 수는 0부터 255까지의 값을 갖게 된다. 네트워크 주소와 네트워크 마스크 역시 같은 형식으로 나타낸다.

IP 네트워크에 대해 올바르게 이해하기 위해서는 위와 같은 주소를 2진수로 이해하면 된다. 즉, 각각의 바이트를 8자리의 이진수로 나타내고, 이를 네 개 붙여놓은(앞에서부터) 32자리의 이진수를 생각해 보자. IP 네트워크에는 기본적으로 2m 개의 컴퓨터(혹은 IP 주소)가 할당될 수 있다. 이 경우의 네트워크 주소는 앞의 32-m 자리가 임의의 수(0 또는 1)로 구성되어 있고, 뒤의 m자리는 0으로 채워지게 된다. 네트워크 마스크는 앞의 32-m 자리가 1로 채워져 있고, 뒤의 m자리는 0으로 채워지게 된다. 이와 같은 IP 네트워크에는 앞의 32-m 자리가 네트워크 주소와 일치하는 모든 IP들이 포함되게 된다.

예를 들어 네트워크 주소가 194.85.160.176이고, 네트워크 마스크가 255.255.255.248인 경우를 생각해 보자. 이 경우, 이 네트워크에는 194.85.160.176부터 194.85.160.183까지의 8개의 IP 주소가 포함된다.

어떤 네트워크에 속해있는 IP 주소들이 주어졌을 때, 네트워크 주소와 네트워크 마스크를 구해내는 프로그램을 작성하시오. 답이 여러 개인 경우에는 가장 크기가 작은(포함되는 IP 주소가 가장 적은, 즉 m이 최소인) 네트워크를 구하도록 한다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 n개의 줄에는 각 컴퓨터의 IP 주소가 주어진다.

출력

첫째 줄에 네트워크 주소를, 둘째 줄에 네트워크 마스크를 출력한다.

예제 입력

예제 출력

접근

이 문제는 네트워크 마스크 즉, 서브넷 마스크를 구하는 문제이다.
서브넷 마스크는 2진수로 되어있어서 문제 분류를 비트마스크로 한 것같지만, 필자는 문자열을 이용해서 이 문제를 해결했다.(파이썬은 정말 문자열 처리에 있어서 편한것 같다)

우선 ip주소는 이진수로 되어있고, 네트워크 주소와 호스트주소가 나눠져있다.
네트워크 마스크는 이진수로 된 ip주소에서 몇자리까지가 네트워크 부분인지를 나타내는 것이다.
네트워크 마스크와 ip주소를 and연산을 하면 네트워크 주소가 나오게 된다.
이를 예를 들어서 설명해보도록 하겠다.

문제에 나온대로 네트워크 마스크를 255.255.255.248, ip주소를 194.85.160.177라고 가정하겠다.
각각을 이진수로 바꾸면 다음과 같다.

255.255.255.248 => 11111111 11111111 11111111 11111000
194.85.160.177 => 11000010 01010101 10100000 10110001

두 수를 and연산하면 너트워크 마스크의 1인 부분이 네트워크 주소, 0인부분이 호스트 부분이 된다.

다시 문제로 돌아가보겠다.
문제에서는 어떤 네트워크에 속해있는 ip주소를 주고 , 네트워크 주소와 네트워크 마스크를 구해내라고 하였고, 이때 답이 여러개이면 ip주소가 가장적은 네트워크를 구하라고 했다.

즉, 호스트부분이 가장적게 나오는 네트워크 마스크를 구하면 된다
호스트부분이 적게 나오는 것은 0인부분이 가장 적으면 된다.

이를 구하기 위해서는 주어진 ip주소를 전부 이진수로 나열하고 각 자리수를 비교한다.
주어진 ip주소는 전부 같은 네트워크 이므로, 네트워크가 가장 커지는 위치, 즉, 각 자리수를 비교해서 처음으로 달라지는 부분전까지를 네트워크 주소로 정하면 된다.

말로 설명하면 어려우니 예를 들어보겠다.
주어진 ip주소를 전부 이진수로 바꾸었다.

194.85.160.177 => 11000010 01010101 10100000 10110001
194.85.160.183 => 11000010 01010101 10100000 10110111
194.85.160.178 => 11000010 01010101 10100000 10110010

진하게 색칠한 곳까지가 모든 ip의 값이 같다.
진하게 색칠한 곳까지가 네트워크 주소가 된다는 뜻이다

뒤의 3개는 호스트 부분을 뜻한다.

이렇게 되면 네트워크 마스크는 진하게 색칠할 곳까지 1로 채우고 나머지 뒤의 3자리는 0으로 채운값이 된다.

네트워크 마스크는 네트워크 부분이 전부 1이고 호스트부분은 전부 0인 값이다.
그래야 and연산 했을때, 1인부분이 네트워크가 나오게 된다.

11111111 11111111 11111111 11111000

위의 값이 주어진 ip중에서 가장 작은 호스트부분을 가지는 네트워크 마스크가 된다.

이제 이 값을 이용해서 입력으로 주어진 ip중에 아무거나 하나를 뽑아서 and 연산을 하면 해당 ip의 네트워크 주소가 나오게 된다.

이를 코드로 구현하는 것은 단순하다.
입력으로 받은 정수를 전부 format()을 이용해서 이진수로 바꾸어서 붙여주었다.

각 값의 첫번째 자리부터 마지막 자리까지 값을 비교하면서 모든 값이 같으면 네트워크 마스크의 값을 저장하는 mask리스트에 값을 1로 변경시켜주면서 진행했다.

값들중 하나라도 달라지게 되면 그 즉시 반복문을 빠져나와서 네트워크 마스크를 이어붙어서 문자열로 만들었다(리스트에 한개씩 넣어둠)

그리고 구한 네트워크 마스크와 주어진 ip값중 첫번째 것을 가져와서 and연산을 하여, 네트워크 주소를 구해주었다.

import sys


'''입력'''
n = int(sys.stdin.readline())
total = list()

for _ in range(n):
    a,b,c,d = map(int,sys.stdin.readline().rstrip().split('.'))
    #전부 8자리를 채워서 이진수 변환 
    total.append(format(a,'08b')+format(b,'08b')+format(c,'08b')+format(d,'08b'))

'''연산'''
#반복문을 돌면서 어디까지 같은지 확인
#서브넷 마스크 업데이트할 리스트, 기본은 전부 0
mask = ['0']*32

for i in range(len(total[0])):
    #값 체크를 위해서 넣음
    temp = total[0][i]
    check = True

    for j in total:
        if temp != j[i]:
            check = False
            break
    #전부 같으면 1
    else:
        mask[i] = '1'
    
    if check is False:
        break

#리스트에 있는 것 이어붙여서 문자열로 만듦
mask_str = ''.join(mask)

#주어진 ip주소중에 첫번째것을 가져와서 구한 마스크값과 &연산
ip_str ='0b'+total[0]
network_address_str = format(int(mask_str,2)&int(ip_str,2),'032b')


#8자리씩 끊어서 저장
network_result = list()

mask_result = list()

#8자리씩 끊음
for i in range(4):
    network_result.append(str(int('0b'+network_address_str[i*8:(i*8)+8],2)))
    mask_result.append(str(int('0b'+mask_str[i*8:(i*8)+8],2)))

print('.'.join(network_result))
print('.'.join(mask_result))

결과

답은 맞긴 맞았는데 출제자의 의도에 맞지 않았던것 같다
ip의 경우 이진수로 되어있기 때문에 비트연산을 이용한 비트마스크로 문제를 풀었어야되는데, 문자열로 풀었다.
(개인적으로는 문자열로 푸는게 뭔가 눈에 더 잘들어와서 좋다)