백준 > Python3 > 2160번 : 그림 비교

이번 포스팅은 그림 비교라는 문제입니다.

사용한 언어는 파이썬3이구요~

아마도 브루트 포스 문제인것 같네요.

 

일단 문제를 한번 보도록하죠!

문제

N(2≤N≤50)개의 그림이 있다.

각각의 그림은 5×7의 크기이고, 두 가지 색으로 되어 있다.

이때 두 가지의 색을 각각 ‘X’와 ‘.’으로 표현하기로 하자.

이러한 그림들이 주어졌을 때, 가장 비슷한 두 개의 그림을 찾아내는 프로그램을 작성하시오.

두 개의 그림에서 다른 칸의 개수가 가장 적을 때, 두 개의 그림이 가장 비슷하다고 하자.

예를 들어 위와 같은 두 개의 그림이 주어졌을 때,

색칠한 부분이 서로 다르게 된다. 위의 그림은 5개의 칸이 서로 다르다.

이와 같이 서로 다른 칸의 개수가 가장 작은 경우를 찾는 것이다.

입출력

입력

첫째 줄에 N이 주어진다. 다음 5×N개의 줄에 7개의 문자로 각각의 그림이 주어진다.

출력

첫째 줄에 가장 비슷한 두 그림의 번호를 출력한다. 그림의 번호는 입력되는 순서대로 1, 2, …, N이다. 번호를 출력할 때에는 작은 것을 먼저 출력한다. 입력은 항상 답이 한 가지인 경우만 주어진다.

 

예제입력1	예제출력1
3 ..X.... .XXX... .XX.... .....X. .X...X. ...X... ..XX... .XX.... .XX..X. .X...X. XX..... X...... XX...XX XXXX.XX XXX..XX	1 2

 

문제풀이

저는 일단 5*7의 배열을 하나의 컨테이너라는 단위로 보고 접근을 했어요.

위의 예제로 본다면 3개의 컨테이너가 있는거죠.

 

이런 방법으로 접근한다면 3개의 컨테이너들을 각각 비교해나가는 문제가 되는거에요.

입력이 굉장히 많아 보이지만 별거 아닌 문제죠!

 

그리고 또 필요한게 이 컨테이너들을 담아놓는 단위이죠.

저는 이걸 박스라고 부르고 리스트로 구현을해서 컨테이너들을 하나씩 하나씩

여기에 담을 거에요.

그러면 입력과정이 끝나면 우리가 받은 컨테이너들을

인덱스로 접근이 가능하게 되겠죠??

 

이제 박스안의 각각의 컨테이너들을 비교해야하는데요.

저는 각각의 요소들을 비교해나가는 과정에서

파이썬의 내장라이브러리 중 하나인 itertools의 combinations라는 함수를 사용했어요!

조합을 만들어내는 함수이죠!

 

itertools.combinations(리스트, 개수)

이 함수의 첫번째 인자로는 리스트가 들어가요. 어떤 대상을 베이스로 조합을 만들지를

함수에 알려주는 인자이구요. 

두번째 인자는 그 중에서 몇개를 선택해서 만들어나갈지를 알려주는 인자입니다.

 

조합이란 중복되지 않는 선택을 말하는건데요.

여기서 조합이 필요한 이유는 모든 컨테이너들간에 비교를 하는데 중복되지 않는 비교를

하기 위함이에요.

예를들어서 1, 2, 3이 있다고 했을때

1 2 / 1 3 / 2 3 이런식으로 비교를 하고 싶은거죠.

순열이라는 함수도 있는데 그 녀석의 경우는 중복이 포함되어서

1 2 와 2 1이 다른 거라고 보고 또 비교를 하게되어서 같은 작업을 반복하게되요.

 

사실 이 문제는 이중 for loop으로도 충분히 풀 수 있는 문제인데

저는 머리에 조합이 먼저 떠올라 이렇게 풀었어요!

 

from itertools import combinations

for i in combinations("ABCDE", 2):
	print(i)

위의 예제 코드를 실행시켜보시면 쉽게 이 함수가 어떤 역할을 하는지

이해하실 수 있을 거에요.

 

제 블로그에서는 궂이 결과값을 보여주지는 않으려고 해요~

이런 코드를 입력해보고 직접 결과값을 봐야지 확실히 이해가 빠르잖아요!

반드시 실행시켜보시고 다른 값으로도 확인해보세요~~

 

다시 문제로 넘어가면 우리는 현재 우리가 가진 컨테이너들의 조합이 필요해요.

그래서 그 조합들에서 서로의 컨테이너들을 비교해나가는 거죠.

 

비교해보고 만약 조합으로 선택된 두 컨테이너의 다른 부분이 더 적다면

이 조합을 선택해 놓으면 되는거에요.

 

이 방식으로 모든 조합을 다 이행하고나서

남아있는 최소값을 만들어낸 조합을 출력해주시면 됩니다^^

 

프로그래밍에서 알고리즘이 차지하는 부분이 상당히 크죠.

하지만 그러한 알고리즘이 사용되는 부분은 적어요. 

적지만 큰 영향을 미치는 거죠. 그래서 무시할 수 없는 부분인거구요.

이 문제는 브루트 포스문제로 많은 입력값을 받아서 처리를 하는 문제인데

이렇게 많은 입력을 받는 코드는 정말 쓸모가 없어요.

그런데 정말 많은 코드에서 쓰일 수 밖에 없죠.

많지만 코드의 퍼포먼스에는 적은 영향을 미치는거죠. 그래서 무시할 수도 있는데요.

 

하지만 저는 이런 부분이 굉장히 중요하다고 생각해요.

이런 코드를 얼마나 빠르게 만들 수 있는지

얼마나 알아보기 쉽게 작성할 수 있는지 

어떤 함수를 사용할지 등등 고려해야하는게 꾀있어요.

 

어떻게 보면 알고리즘은 코딩에서 멋있고 화려한 기술이고

입출력은 지루한 기본기라고 볼 수도 있겠죠.

 

예전에 처음 시작할때는 입출력시에 여러가지 방법으로

시도해보고 코드 효율성이나 가독성에 신경을 썼는데

이제는 그냥 떠오르는데로 적고 지나가네요 ㅎ 

하지만! 처음 하시는 분들은 꼭 명심하세요.

이 부분이 안중요하다고 코드 복붙하시는 분이 있다고 하신다면

저는 오히려 이부분을 직접구현하시고

알고리즘 부분을 복붙하라고 말씀드리고 싶네요.

 

지루하지만 이걸 잘하게 되면 알고리즘에 점점 다가가고 있다는걸

느끼실 수 있을꺼에요.

 

import itertools

def comp_line(x,y): #라인 비교
    result=0
    for i in range(7):
        if x[i]!=y[i]:
            result+=1
    return result

def comp_container(x,y): #컨테이너 비교
    result=0
    for i in range(5):
        result+=comp_line(x[i],y[i])
    return result

box=[]
for i in range(int(input())):
    container=[]
    for j in range(5):
        container+=input(),
    box+=container,

mn=35
result=[0,0]
for i in itertools.combinations(range(len(box)),2):
    val=comp_container(box[i[0]],box[i[1]])
    if val<mn:
        mn=val
        result[0],result[1]=i[0]+1,i[1]+1
print(*result)

 

http://acmicpc.net/problem/2160

2160번: 그림 비교