Faits: A. C._, né en 1952, est propriétaire d'une entreprise agricole sise à X._. Le 12 mars 2009, il a conclu avec les cousins A._ et B._, agriculteurs, un contrat de bail à ferme pour entreprise agricole portant sur une surface de 16,5 hectares et des bâtiments agricoles, sans l'habitation principale. La durée du contrat a été fixée à douze ans et le fermage à 23'700 fr. Par courrier du 19 mars 2009, A._ et B._ ont demandé l'approbation du bail à l'Autorité foncière cantonale fribourgeoise (ci-après: l'Autorité foncière). Le 22 avril 2009, lors d'une inspection des lieux par une délégation de l'Autorité foncière, il fut constaté que C._ et sa famille occupaient l'habitation et qu'ils n'avaient pas l'intention de la quitter. Le bailleur a également indiqué, à cette occasion, qu'il ne voulait plus affermer ses terres. C._, le 30 avril 2009, a confirmé à l'Autorité foncière son intention de se retirer du contrat. Son fils D._ a, le même jour, également écrit à cette autorité pour affirmer qu'il terminait une formation d'agriculteur et qu'il souhaitait reprendre le domaine à bref délai. Il a dès lors demandé que l'autorisation sollicitée ne soit pas accordée. Pour leur part, les cousins A._ et B._ ont précisé, le 13 mai 2009, qu'ils avaient d'ores et déjà procédé à d'importants investissements à la suite de la conclusion du contrat. Le 19 mai 2009, l'Autorité foncière a constaté que C._ renonçait à ce qu'il soit statué sur l'autorisation d'affermage par parcelles de son domaine agricole. Elle a également refusé d'approuver, en l'état, le fermage de cette entreprise agricole, les parties étant invitées à saisir le juge civil pour que celui-ci examine la validité du contrat qu'elles avaient conclu. Le 25 juin 2009, A._ et B._ ont déposé une demande de reconsidération de la décision du 19 mai 2009, arguant que le juge civil avait été saisi de la cause au fond. Par décision du 16 juillet 2009, l'Autorité foncière a refusé d'autoriser l'affermage par parcelles de l'entreprise agricole propriété de C._ et a résilié le contrat de bail conclu le 12 mars 2009 pour la fin février 2010. A l'appui de cette décision, l'Autorité foncière a tout d'abord retenu que la maison d'habitation était liée à l'exploitation et qu'elle constituait un élément important de celle-ci. Par ailleurs, selon elle, aucune des conditions légales n'était en l'espèce réalisée pour autoriser l'affermage des terres seules sans cet immeuble. B. Recourant contre cette décision auprès de la Cour administrative du Tribunal cantonal du canton de Fribourg (ci-après: le Tribunal cantonal), A._ et B._ ont pour l'essentiel fait valoir que la maison d'habitation, liée à l'entreprise agricole, n'était pas indispensable à l'exploitation, dans la mesure où elle était d'ores et déjà en partie louée à un tiers. En outre, le domaine de C._ était voisin de celui de A._ et du lieu où il résidait, tout en étant au surplus situé à un kilomètre du domicile de B._. Dans la mesure où, en définitive, les biens pris à bail formaient d'ores et déjà une entreprise agricole sans l'habitation, une autorisation n'était pas nécessaire pour l'affermage de cette entreprise. Selon eux, subsidiairement, le bail ayant été conclu pour une durée de douze ans, il s'agirait d'un affermage par parcelles temporaire; les conditions légales d'un tel affermage étant réalisées, l'autorisation devait leur être accordée. C._ a produit le jugement du 16 juin 2010 du Président du Tribunal civil de la Veveyse l'autorisant, par mesures provisionnelles, à laisser paître son bétail aux endroits indiqués par les cousins A._ et B._; il a également déposé une lettre de son fils D._ confirmant la volonté de celui-ci de reprendre l'exploitation familiale, de même que le certificat de capacité d'agriculteur que celui-ci avait obtenu en 2010. Par jugement du 30 septembre 2011, le Tribunal cantonal a rejeté le recours. A cette occasion, il a notamment retenu, en se référant au rapport du 22 avril 2009 de la délégation de l'Autorité foncière, que la maison d'habitation, les bâtiments agricoles et les terres formaient une unité économique agricole, le domaine étant "d'un seul mas autour de la ferme". Le Tribunal cantonal a également pris en compte des faits ultérieurs à la conclusion du contrat de base, tel que l'accord conclu par les parties en cours de procédure permettant à C._, qui continuait à vivre dans l'habitation, de conserver les terres nécessaires à l'affouragement de son bétail, soit environ 4 hectares sur 16,5 hectares. Tant la distraction de l'habitation que des 4 hectares de terrain agricole nécessitaient, selon le Tribunal cantonal, la soumission à la procédure d'autorisation du droit sur le bail à ferme agricole. Or, les conditions présidant à l'octroi de cette autorisation n'étaient pas remplies. Le Tribunal cantonal a fixé un délai au 31 mars 2012 aux recourants pour évacuer le domaine. C. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent au Tribunal fédéral, sous suite de frais et dépens, principalement, de constater que le contrat de bail à ferme a pour objet une entreprise agricole au sens du droit foncier rural et qu'il n'est, partant, pas soumis à la procédure d'autorisation d'affermage par parcelles et de renvoyer la cause à l'Autorité foncière pour décision d'approbation du fermage. Subsidiairement, ils requièrent d'approuver le contrat d'affermage par parcelles temporaire de l'entreprise agricole, avec une échéance au 31 mars 2021 et de renvoyer la cause à l'Autorité foncière pour décision d'approbation du fermage. Plus subsidiairement, ils demandent d'annuler la décision du Tribunal cantonal confirmant la résiliation du contrat de bail à ferme agricole pour le 28 février 2010 et de renvoyer la cause à l'Autorité foncière pour nouvelle décision de résiliation conforme au droit sur le bail à ferme agricole. C._, le Tribunal cantonal et l'Autorité foncière, comme l'Office fédéral de la justice, concluent au rejet du recours. Par ordonnance du 6 décembre 2011, le Président de la IIe Cour de droit public du Tribunal fédéral a octroyé l'effet suspensif au recours. 